ask for the number that has 13 and is divisible by 13
Obviously, the current four states cannot fully answer the question. Regarding whether it can be 13 Divide it is necessary to add a mod status
When pre is 2, it means that 13 has already existed (directly inherited). When pre is 1, it means that the previous one is 1. When pre is 0, it means that the previous one is not. 0
After I did this, I found it was still wrong
Adding one dimension requires adding to the dp array because the state transition is indispensable! ! ! ! ! ! ! ! !
This will go smoothly ac
#include
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
/////////////////////////////////< /span>/
#define inf 0x3f3f3f3f
#define N 10+5
ll dp[N][20][10 ];
ll a[N];
ll dfs(int pos,int pre,< span style="color: #0000ff;">int mod,bool lead,bool limit)
{
if(!pos)
{
if(mod==0&&pre==< span style="color: #800080;">2)return 1;
else return 0;
}
if(!limit&&!lead&&dp[pos][mod][pre]!=-1)return dp[pos][mod][pre];
ll ans=0;
int up=limit?a[pos]:9;
rep(i,0,up)
{
if( (pre==1&&i== 3) ||pre==2)
ans+=dfs(pos-1,2 ,(mod*10+i)%13,lead&&i==0,limit&&i==a[pos]);
else
ans+=dfs(pos-1,i==1< /span>?1:0,(mod*10+i)%13,lead&&i==0,limit&&i==a[pos]);
}
if(!limit&&!lead)dp[pos][mod][pre]=ans;
return ans;
}
ll solve(ll x)
{
int pos=0;
while(x)
{
a[++pos]=x%10;
x/=10;
}
return dfs(pos,0,0,true,true );
}
int main()
{
ll x;
while(scanf("%lld",&x)==1)
{
CLR(dp,-1);
printf("%lld ",solve(x));
}
return 0;
}
#include
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
/////////////////////////////////< /span>/
#define inf 0x3f3f3f3f
#define N 10+5
ll dp[N][20][10 ];
ll a[N];
ll dfs(int pos,int pre,< span style="color: #0000ff;">int mod,bool lead,bool limit)
{
if(!pos)
{
if(mod==0&&pre==< span style="color: #800080;">2)return 1;
else return 0;
}
if(!limit&&!lead&&dp[pos][mod][pre]!=-1)return dp[pos][mod][pre];
ll ans=0;
int up=limit?a[pos]:9;
rep(i,0,up)
{
if( (pre==1&&i== 3) ||pre==2)
ans+=dfs(pos-1,2 ,(mod*10+i)%13,lead&&i==0,limit&&i==a[pos]);
else
ans+=dfs(pos-1,i==1< /span>?1:0,(mod*10+i)%13,lead&&i==0,limit&&i==a[pos]);
}
if(!limit&&!lead)dp[pos][mod][pre]=ans;
return ans;
}
ll solve(ll x)
{
int pos=0;
while(x)
{
a[++pos]=x%10;
x/=10;
}
return dfs(pos,0,0,true,true );
}
int main()
{
ll x;
while(scanf("%lld",&x)==1)
{
CLR(dp,-1);
printf("%lld ",solve(x));
}
return 0;
}