【codejam2008

题目大意：

输入一个长度最长为40位的数，再中间插入一些’+’或’-‘，使整个式子结果可以被2或3或5或7整除，有多少种方法达到目标。

题解：

考虑处理2,3,5,7的余数， 可以处理 2×3×5×7=210 的余数。 dp[i][j]表示前i位除以210余j的方案数。

dp[i][j]=∑k=1idp[k−1][(j−num(k,i)+210)mod210]+dp[k−1][(j+num(k,i))mod210] 初始 dp[i][num(1,i)mod210]=1

代码：

#include<cstdio> #include<cstdlib> #include<cstring> #define MAXL 42 #define MODP 210 long long dp[MAXL][MODP]; char num[MAXL]; int getnum(int x,int y) { int res=0; for(int i=x;i<=y;i++) res=(res*10+num[i]-'0')%210; return res; } int main() { int N,len; scanf("%d",&N); for(int Case=1;Case<=N;Case++) { scanf("%s",num+1); len=strlen(num+1); memset(dp,0,sizeof dp); for(int j=1;j<=len;j++) dp[j][getnum(1,j)]++; for(int j=1;j<=len;j++) for(int r=0;r<210;r++) for(int k=1;k<=j;k++) { int x=getnum(k,j); dp[j][r]+=dp[k-1][(r-x+210)%210]+dp[k-1][(r+x)%210]; } long long ans=0; for(int r=0;r<210;r++) if(r%2==0||r%3==0||r%5==0||r%7==0) ans+=dp[len][r]; printf("Case #%d: %I64d\n",Case,ans); } return 0; }