Codeforces908G. New Year and Original Order

给n<=10^700，问1到n中每个数在各数位排序后得到的数的和。答案膜1e9+7。

一看就是数位DP啦。。然而并没有什么思路。。

可以尝试统计n(i,j)表示数j在第i位的出现次数，知道了这个数组后就可以算答案了。可以枚举j，做一次DP，f(a,b,0/1)--考虑第a~n个数，有b个j，是否大于给定数字（因为当前大于给定数字不一定dp到前面的数就大于，所以当前大于给定数字的数也是有贡献的），等等光知道有多少j并不能确定第i位是否有j，行不通。

套路--k(i,j)表示第i位出现的>=j的数字的出现次数，则$n(i,j)=k(i,j)-k(i,j+1)$。现在f(a,b,0/1)中的b则表示有b个>=j的数，那么就可以递推了。用$X_a$表示给定数字第a位是谁：

1、$j>X_a$：$f(a,b,0)=(f(a+1,b,0)+f(a+1,b,1))*X_a+f(a+1,b,0),f(a,b,1)=(f(a+1,b-1,0)+f(a+1,b-1,1))*(10-j)+(f(a+1,b,0)+f(a+1,b,1))*(j-X_a-1)+f(a+1,b,1)$

2、$j<=X_a$：$f(a,b,0)=(f(a+1,b,0)+f(a+1,b,1))*j+(f(a+1,b-1,0)+f(a+1,b-1,1))*(X_a-j)+f(a+1,b-1,0),f(a,b,1)=(f(a+1,b-1,0)+f(a+1,b-1,1))*(10-X_a-1)+f(a+1,b-1,1)$。

还没完，边界条件：1、$j>X_n$：$f(n,0,0)=X_a+1,f(n,0,1)=j-X_a-1,f(n,1,1)=10-j,f(n,1,0)=0$。

2、$j<=X_n$：$f(n,0,0)=j,f(n,0,1)=0,f(n,1,0)=X_n-j+1,f(n,1,1)=10-X_n-1$。

这些加一减一、取等取不等的特别注意。把<和=归在一类是之前在草稿纸上推过发现可以合的。

然后就没了。注意检查膜。

 //#include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<map>

 //#include<bitset>

 #include<algorithm>

 //#include<cmath>

 using namespace std;

 int n;

 #define maxn 711

 char s[maxn];

 const int mod=1e9+;

 int kk[maxn][],f[maxn][maxn][];

 int main()

 {

     scanf("%s",s+); n=strlen(s+);

     for (int j=;j<=;j++)

     {

         int num=s[n]-'';

         if (j>num) {f[n][][]=num+; f[n][][]=; f[n][][]=j-num-; f[n][][]=-j;}

         else {f[n][][]=j; f[n][][]=num-j+; f[n][][]=; f[n][][]=-num-;}

         for (int a=n-;a;a--)

         {

             int num=s[a]-'';

             if (j>num)

             {

                 f[a][][]=(1ll*(f[a+][][]+f[a+][][])*num+f[a+][][])%mod;

                 f[a][][]=(1ll*(f[a+][][]+f[a+][][])*(j-num-)+f[a+][][])%mod;

                 for (int b=,to=n-a+;b<=to;b++)

                 {

                     f[a][b][]=(1ll*(f[a+][b][]+f[a+][b][])*num+f[a+][b][])%mod;

                     f[a][b][]=(1ll*(f[a+][b-][]+f[a+][b-][])*(-j)

                     +1ll*(f[a+][b][]+f[a+][b][])*(j-num-)+f[a+][b][])%mod;

                 }

             }

             else

             {

                 f[a][][]=(1ll*(f[a+][][]+f[a+][][])*j)%mod;

                 f[a][][]=;

                 for (int b=,to=n-a+;b<=to;b++)

                 {

                     f[a][b][]=(1ll*(f[a+][b][]+f[a+][b][])*j

                     +1ll*(f[a+][b-][]+f[a+][b-][])*(num-j)+f[a+][b-][])%mod;

                     f[a][b][]=(1ll*(f[a+][b-][]+f[a+][b-][])*(-num-)+f[a+][b-][])%mod;

                 }

             }

         }

         for (int i=n;i;i--) f[][i][]+=f[][i+][],f[][i][]-=f[][i][]>=mod?mod:,kk[i][j]=f[][i][];

     }

     int ans=;

     for (int i=,ten=;i<=n;i++)

     {

         for (int j=;j<=;j++)

             ans+=1ll*(kk[i][j]-kk[i][j+]+mod)*ten%mod*j%mod,

             ans-=ans>=mod?mod:,ans+=ans<?mod:;

         ten=1ll*ten*%mod;

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

Codeforces908G. New Year and Original Order

最新文章

热门文章