【数位DP】[LOJ10168] 恨7不成妻

短命女 2023-06-01 06:09 7阅读 0赞

还是数位DP...

状态：$f\[x\]\[val\]\[sum\]$表示当前第x位，当前数字为val，当前各位数字和为sum

观察到$val$,$sum$过大，很套路地模7即可...

每个状态存储三个要用到的值：

①cnt:表示满足条件的数字的个数

②s:表示满足条件的数字的和

③s\_2:表示满足条件的数字的平方的和

关于转移：

①cnt的转移就和一般的数位DP一样

②s的转移：因为当前位搞到真实的数字里是$i\*10^x$，而且这一位会被加上cnt次

③s\_2的转移：这个有点烦，我们把$(x+y)^2$展开有$x^2+2xy+y^2$，其中$x=i\*10^x$而y就是下一层搜索结果的s\_2的值

具体细节看代码（看不懂的可以把取模操作去掉看一下主要是写完了我自己都看不懂了）

1 #include<bits/stdc++.h>
     2 #define int long long
     3 #define writeln(x)  write(x),puts("")
     4 #define writep(x)   write(x),putchar(' ')
     5 using namespace std;
     6 inline int read(){
     7     int ans=0,f=1;char chr=getchar();
     8     while(!isdigit(chr)){
        if(chr=='-') f=-1;chr=getchar();}
     9     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    10     return ans*f;
    11 }void write(int x){
    12     if(x<0) putchar('-'),x=-x;
    13     if(x>9) write(x/10);
    14     putchar(x%10+'0');
    15 }const int M = 20 ,mod = 1e9+7;
    16 int l,r,T,a[M],p[M];
    17 struct P{
        int cnt,s,s_2;}f[M][M][M];
    18 P dfs(int x,int val,int sum,int lim){
    19     if(!x)return (P){val&&sum,0,0};
    20     if(!lim&&f[x][val][sum].cnt!=-1)return f[x][val][sum];
    21     register long up=lim?a[x]:9;P ans=(P){
        0,0,0};
    22     for(int i=0;i<=up;++i)
    23         if(i!=7){
    24             P t=dfs(x-1,(val*10+i)%7,(sum+i)%7,lim&&i==a[x]);
    25             ans.cnt=(ans.cnt+t.cnt)%mod;
    26             ans.s=((i*p[x]%mod*t.cnt%mod+t.s)%mod+ans.s)%mod;
    27             ans.s_2=(ans.s_2+(t.s_2+(2*p[x]%mod*i%mod*t.s%mod+p[x]*p[x]%mod*i%mod*i%mod*t.cnt%mod)%mod)%mod)%mod;
    28         }
    29     if(!lim)f[x][val][sum]=ans;
    30     return ans;
    31 }
    32 inline int Solve(int x){
    33     int len=0;
    34     while(x)a[++len]=x%10,x/=10;
    35     return dfs(len,0,0,1).s_2;
    36 }
    37 signed main(){
    38     memset(f,-1,sizeof(f));p[1]=1;
    39     for(register long i=2;i<=19;++i)p[i]=(p[i-1]*10)%mod;
    40     register long T=read();
    41     while(T--){
    42         l=read(),r=read();
    43         writeln(((Solve(r)-Solve(l-1))%mod+mod)%mod);
    44     }return 0;
    45 }

转载于:https://www.cnblogs.com/zhenglw/p/11587928.html