首页 > 代码库 > HDU 4507 有点复杂却不难的数位DP
HDU 4507 有点复杂却不难的数位DP
首先来说，，这题我wrong了好几次，代码力太弱啊。。很多细节没考虑。。
题意：给定两个数 L R，1 <= L <= R <= 10^18 ；求L 到 R 间 与 7 无关的数的平方和
什么数与7 无关？
1 没有数字7
2 不是7的倍数
3 所有数字的和不是7的倍数
我们先来考虑一下 如果这题问的是： L 到 R 间 与7 无关的数有多少个？
这道题该怎么思考？ 给一点提示 dp 方程可以写成三维的 num（i,j,k） 其中 i 代表数的位数 j 代表 这个数对7取模的余数 k 代表这个数所有数字和对7取模的值，至于num(i,j,k) 当让就是这种数的个数了, 方程的转化也很简单 从数末尾逐步填数字 l （0~9）的话 num(i+1,(j*10+l)%7,(k+l)%7)+=num(i,j,k);
接下来 我默认你知道 num[i][j][k] 该怎么求了 这个时候 再来考虑一下 L 到 R 间与7 无关的数的和 ？ 这个时候不用考虑的太复杂，，因为首先，你在求num[i][j][k]的时候已经求出了所有的满足条件的数的所有可能，要求和，无非就是哪一位的那个数字有多少个。
如果我们的dp是逐步往数的末尾填数 ，这个时候可以这样写 sum(i,j,k)其中i,j,k和num的i,j,k一个意思，然后sum表示满足这种情况的数的和 方程的转换可以写为：同样从数末尾逐步填数字 l （0~9）-- num(i+1,(j*10+l)%7,(k+l)%7)+=sum(i,j,k)*10+num(i,j,k)*l;
再来考虑平方和就比较容易了，，我们知道如果前面的数是a 我们往后面塞一个数字l 那么我们要求的数的平方和是---（10*a+l）^2 也就是100*a*a+20*a*l+l*l
方程我就不写了，，然后接下来的思路都是和上面的类似
贴出渣渣的代码。。。
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include <string> 5 #include <cmath> 6 #include <algorithm> 7 #include <map> 8 #include <set> 9 #include <queue> 10 #include <stack> 11 #include<stdlib.h> 12 #include <vector> 13 using namespace std; 14 #pragma comment(linker, "/STACK:1024000000,1024000000") 15 #define ll __int64 16 #define CL(a,b) memset(a,b,sizeof(a)) 17 #define MAXNODE 100010 18 ll MOD=1000000007; 19 20 ll s,e; 21 22 ll dp[30][7][7]; 23 ll wsu[30][7][7]; 24 ll num[30][7][7]; 25 ll val[30]; 26 void initval() 27 { 28 int i=0; 29 val[1]=1; 30 val[0]=0; 31 for(i=2;i<=19;i++) 32 { 33 val[i]=val[i-1]*10; 34 } 35 } 36 37 void initdp() 38 { 39 int i,j,k,l; 40 CL(dp,0); 41 CL(num,0); 42 CL(wsu,0); 43 for(i=0;i<10;i++) 44 { 45 if(i==7)continue; 46 dp[1][i%7][i%7]+=i*i; 47 wsu[1][i%7][i%7]+=i; 48 num[1][i%7][i%7]++; 49 } 50 num[0][0][0]=1; 51 for(i=1;i<29;i++) 52 { 53 for(j=0;j<7;j++) 54 { 55 for(k=0;k<7;k++) 56 { 57 for(l=0;l<10;l++) 58 { 59 if(l==7)continue; 60 num[i+1][(j+l)%7][(k*10+l)%7]+=num[i][j][k]%MOD; 61 num[i+1][(j+l)%7][(k*10+l)%7]%=MOD; 62 wsu[i+1][(j+l)%7][(k*10+l)%7]+=(wsu[i][j][k]*(ll)10+(ll)l*(num[i][j][k]))%MOD; 63 wsu[i+1][(j+l)%7][(k*10+l)%7]%=MOD; 64 dp[i+1][(j+l)%7][(k*10+l)%7]+=(((ll)l*(ll)l*num[i][j][k])+dp[i][j][k]*100+(ll)2*(ll)l*wsu[i][j][k]*(ll)10)%MOD; 65 dp[i+1][(j+l)%7][(k*10+l)%7]%=MOD; 66 } 67 // printf("%d %d %d %I64d\n",i,j,k,dp[i][j][k]); 68 } 69 } 70 } 71 } 72 73 ll pro(ll n) 74 { 75 if(n==0)return 0; 76 ll rem=0; 77 ll nu[30]; 78 int w,i,j,k; 79 nu[0]=0; 80 ll tem=n,va;w=1,rem=0; 81 while(tem!=0) 82 { 83 nu[w]=tem%10; 84 tem/=10; 85 w++; 86 } 87 va=0; 88 int su=0; 89 ll v=0; 90 while(--w) 91 { 92 if(nu[w]==7) 93 { 94 for(i=1;i<w;i++)nu[i]=9; 95 nu[w]=6; 96 } 97 for(i=nu[w]-1;i>=0;i--) 98 { 99 if(i==7)continue;100 for(j=0;j<7;j++)101 {102 for(k=0;k<7;k++)103 {104 if((su+i+j)%7==0)continue;105 if(((ll)v+(ll)i*val[w]+(ll)k)%7==0)continue;106 ll pre=(va+(ll)i*(val[w]%MOD))%MOD;107 pre%=MOD;108 rem+=(((pre*pre)%MOD)*(num[w-1][j][k]%MOD))%MOD;109 rem%=MOD;110 rem+=dp[w-1][j][k]%MOD;;111 rem%=MOD;112 rem+=((((ll)2*pre)%MOD)*wsu[w-1][j][k]%MOD)%MOD;113 rem%=MOD;114 }115 }116 }117 rem%=MOD;118 va+=(nu[w]*(val[w]%MOD))%MOD;119 va%=MOD;120 v+=nu[w]*(val[w]%7);121 v%=7;122 su+=nu[w];123 su%=7;124 }125 if(v!=0&&su!=0)rem+=(va*va)%MOD;126 return rem%MOD;127 }128 129 int main()130 {131 int tt;132 initval();133 initdp();134 scanf("%d",&tt);135 while(tt--)136 {137 scanf("%I64d %I64d",&s,&e);138 ll rs=pro(s-1LL);139 ll re=pro(e);140 ll rem=re-rs;141 rem=rem%MOD;142 if(rem<0)rem+=MOD;143 // printf("%I64d %I64d ",rs,re);144 printf("%I64d\n",rem);145 }146 return 0;147 }
HDU 4507 有点复杂却不难的数位DP