首页 > 编程知识 正文

未来数位官网,江苏7数位

时间:2023-05-06 12:35:40 阅读:286351 作者:4112

【分析】
挺神奇(套路)的表示状态
感觉自己有点入门了…(但愿不是错觉)
dp[i][j][k][l]表示i位数字,最高位为j,除以13的余数为k,且包含13的数字个数

【代码】

//hdu 3652 数位dp #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define ll long long#define M(a) memset(a,0,sizeof a)#define fo(i,j,k) for(i=j;i<=k;i++)using namespace std;int n,m;ll dp[15][10][15][2],pw[15],digit[15];inline ll work(int n){ ll i,j,k,len=0,ans=0,now=0,flag=0; memset(digit,0,sizeof digit); while(n) digit[++len]=n%10,n=n/10; for(i=len;i>=1;i--) { fo(j,0,digit[i]-1) { ans+=dp[i][j][(13-now)%13][1]; if(flag || (digit[i+1]==1 && j==3)) ans+=dp[i][j][(13-now)%13][0]; } now=(now+digit[i]*pw[i-1])%13; if(digit[i+1]==1 && digit[i]==3) flag=1; } return ans;}int main(){ ll i,j,k,x; dp[0][0][0][0]=1; pw[0]=1; fo(i,1,12) pw[i]=pw[i-1]*10; fo(i,1,10) fo(j,0,9) fo(k,0,12) fo(x,0,9) //上一位的数字 { int tmp=(k-j*pw[i-1]%13+13)%13; if(!(j==1 && x==3)) dp[i][j][k][0]+=dp[i-1][x][tmp][0]; dp[i][j][k][1]+=dp[i-1][x][tmp][1]; if(j==1 && x==3) dp[i][j][k][1]+=dp[i-1][x][tmp][0]; } while(scanf("%d",&n)!=EOF) printf("%lldn",work(n+1)); return 0;}

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。