hdu4507 吉哥系列故事——恨7不成妻

吉哥系列故事——恨7不成妻Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1059 Accepted Submission(s): 328


Problem DescriptionInputOutputSample InputSample Output#include <stdio.h>#include <string.h>using namespace std;#define M 100int pri[M];#define MOD 1000000007struct node { __int64 cnt,s1,s2; node(__int64 tcnt=0,__int64 ts1=0,__int64 ts2=0){ cnt=tcnt,s1=ts1,s2=ts2; }}dp[M][7][7][3];bool flag[M][7][7][3];__int64 ten[30];node dfs(int pos,int t,int s,int mod,int f){ if(pos==0){ if(t||mod==0||s==0) return node(0,0,0); return node(1,0,0); } if(!f&&flag[pos][s][mod][t])return dp[pos][s][mod][t]; int u=f?pri[pos]:9; node ans; for(int i=0;i<=u;i++){ node temp=dfs(pos-1,t||i==7,(s+i)%7,(mod*10+i)%7,f&&i==u); ans.cnt=(ans.cnt+temp.cnt)%MOD; __int64 k=i*ten[pos-1]%MOD; ans.s1=(temp.cnt*k%MOD+temp.s1+ans.s1)%MOD; ans.s2=(k*k%MOD*temp.cnt%MOD+k*temp.s1%MOD*2+temp.s2+ans.s2)%MOD; } if(!f)flag[pos][s][mod][t]=true,dp[pos][s][mod][t]=ans; return ans;}__int64 solve(__int64 x){ int cnt=0; while(x){ pri[++cnt]=x%10;x/=10; } node temp=dfs(cnt,0,0,0,1); return temp.s2;}int main(){ int tcase; __int64 l,r; memset(flag,false,sizeof(flag)); ten[0]=1; for(int i=1;i<30;i++) ten[i]=ten[i-1]*10%MOD; scanf("%d",&tcase); while(tcase--){ scanf("%I64d%I64d",&l,&r); printf("%I64d\n",(solve(r)-solve(l-1)+MOD)%MOD); } return 0;}