hdu4507 吉哥系列故事——恨7不成妻[数位DP]

这题面什么垃圾玩意儿

首先看到问题格式想到数位DP，但是求的是平方和。尝试用数位DP推出。

先尝试拼出和。设$f[len][sum][mod]$表示填到$len$位，已填位置数位和$sum$，数字取余为$mod$时候的方案数，$g[len][sum][mod]$表示在这种情况下的所有满足要求的数的和（指的是后面剩余空位部分的数的和，前面填好的是不算的）。

那么枚举所填的数$i$，对于每一个满足要求的$x$，填上一个$i$之后变为

$10^{len-1}i+x$

（下$f[len-1][(sum+i)\mod 7][(10mod+i)\mod 7]$简记$f'$，$g,h$同理）

于是对于每一个$i$都有一次累加作用，这些$x$的和推过来应当是

$g[len][sum][mod]=\sum\limits_{i} (10^{len-1}if'+g')$

于是就完成了$g$的递推。$h$表示后面空位的数的平方和，也类似推法。

$h[len][sum][mod]=\sum\limits_{i} (10^{len-1})^2 i^2 f' + \sum\limits_{i} 2\times 10^{len-1} i f' + g'$

然后再每一次$i$的dfs完成之后进行递推。

注意这里的实现有一个小技巧，把$f,g,h$全部放结构体里，这样dp完一次之后直接取get他的整个包$f,g,h$，就不用考虑什么卡上界或者费事记录额外的东西了。

WA1：longlong输入又忘了。。

WA2：取模好好写。。不要老想着减少取模，不然会漏考虑的，万一真的要避免取模应当严格讨论加减乘除数的范围。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define dbg(x) cerr << #x << " = " << x <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int P=1e9+;

 int bin[],bin2[];

 struct thxorz{

     int f,g,h;

     thxorz(int f=-,int g=,int h=):f(f),g(g),h(h){}

 }f[][][];

 int b[];

 int T;

 ll L,R;//mistake

 thxorz dp(int len,int sum,int mod,int limit){

     if(!len)return thxorz(sum&&mod,,);

     if(!limit&&~f[len][sum][mod].f)return f[len][sum][mod];

     int num=limit?b[len]:;

     thxorz ret,tmp;ret.f=;

     for(register int i=;i<=num;++i)if(i^){

         tmp=dp(len-,(sum+i)%,(mod*+i)%,limit&&i==num);//mistake2

         ret.f+=tmp.f;ret.f>=P&&(ret.f-=P);

         ret.g=(tmp.g+bin[len-]*1ll*tmp.f%P*i+ret.g)%P;

         ret.h=(bin2[len-]*1ll*tmp.f%P*i*i+tmp.h+*bin[len-]*1ll*tmp.g%P*i+ret.h)%P;

     }

     return limit?ret:f[len][sum][mod]=ret;

 }

 inline int solve(ll x){

     int len=;while(x)b[++len]=x%,x/=;

     return dp(len,,,).h;

 }

 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);

     for(register int i=,res=;i<=;++i,res=res*1ll*%P)bin[i]=res,bin2[i]=res*1ll*res%P;

     read(T);while(T--)read(L),read(R),printf("%d\n",(solve(R)-solve(L-)+P)%P);

     return ;

 }

巴特西

hdu4507 吉哥系列故事——恨7不成妻[数位DP]

最新文章

热门文章