题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4669
考察对取模的的理解深不深刻啊，当然还有状态的设计····设d[i][j]表示以第i个数结尾，余数为j的取法数，那么在第i个数后加一个数
那么有递推式int yu =( j * log10( a[i+1] ) + a[i+1] )%k,
d[i+1][yu] += d[i][j] .考虑到这是一个环这样多生成了一个余数，这个余数应该减去，还有++d[i+1][a[i+1]%k].
贴代码：
1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #define N1 50005 5 #define N2 205 6 int dp[N1][N2]; 7 int a[N1],b[N1],e[N1*3]; 8 int solve(int n,int k) 9 { 10 e[0]=1; 11 for(int i=1; i<=n*3; ++i)//e[i]存的是10^i%k 12 e[i] = e[i-1]*10%k; 13 for(int i=0; i<n; ++i)//初始化dp为0 14 for(int j=0; j<k; ++j) 15 dp[i][j] =0; 16 for(int i=1; i<=n; ++i) 17 { 18 scanf("%d",&a[i]); 19 b[i] = log10(a[i])+1;//b[i]存的是每一个数有多少位 20 } 21 int s =0; 22 int len=0;// 预处理出以第n个数结尾,余数为j取法数 23 for(int i=n; i > 0; --i) 24 { 25 s = (a[i]*e[len]+s)%k; 26 ++dp[0][s]; 27 len += b[i]; 28 } 29 int ans= dp[0][0]; 30 for(int i=1; i<n; ++i) 31 { 32 for(int j=0; j<k; ++j) 33 dp[i][(j*e[b[i]]+a[i])%k] += dp[i-1][j]; 34 s = (s*e[b[i]]+a[i])%k;//这是一个不合法的余数 35 //如9 6 4 2 8 （9 6 4 2 8）这个余数是964289%k 36 --dp[i][s]; 37 ++dp[i][a[i]%k];//独立的 38 s = ((s-a[i]*e[len])%k+k)%k; 39 //计算64289的余数，因为(9*10^len + 64289)%k = s 40 //那么64289%k = ((s-a[i]*e[len])%k+k)%k; 41 ans += dp[i][0]; 42 } 43 return ans; 44 } 45 int main() 46 { 47 // freopen("1004.txt","r",stdin); 48 int n,k; 49 while(scanf("%d%d",&n,&k) != EOF) 50 { 51 printf("%d ",solve(n,k)); 52 } 53 return 0; 54 }