[Codeforces908G][DP]New Year and Original Order

翻译

定义S(x)表示x的数位从小到大排序后得到的值
如S(505)=55,S(43231)=12334
求$\sum S(i)$，$i<=n,n<=10^{700}$

题解

很套路的东西
考虑把贡献拆开
比如
11122233344
11111111111
—111111111
---------11111
--------------11
对于1，上例有11个大于等于他的数
所以他对于这个例子的贡献是$11....11$(11个1)
对于2，上例有8个大于等于他的数
所以他对于这个例子的贡献是$11....11$(8个1)
以此类推
那你就可以设状态$f[i][j][k][l]$表示前i位，有j个大于等于K的数位，是否卡上界
数位DP一下即可

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<vector> #include<ctime> #include<map> #define LL long long #define mp(x,y) make_pair(x,y) #define mod 1000000007 using namespace std; inline int read() {
     int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
     x=x*10+ch-'0';ch=getchar();}return x*f; } inline void write(int x) {
     if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0'); } inline void print(int x){
     write(x);printf(" ");} LL f[710][710][12][2]; void ad(LL &x,LL y){
     x+=y;if(x>=mod)x-=mod;} int pa[710]; LL dp(int pos,int num,int dight,int op) {
     if(num<0)return 0;if(!pos)return (num==0);if(f[pos][num][dight][op]!=-1)return f[pos][num][dight][op];LL ret=0;int lim=op?pa[pos]:9;for(int i=0;i<=lim;i++)ad(ret,dp(pos-1,num-(i>=dight),dight,op&(i==lim)));return f[pos][num][dight][op]=ret; } char ch[710]; LL sum[710]; int main() {
     scanf("%s",ch+1);int len=strlen(ch+1);for(int i=1;i<=len;i++)pa[len-i+1]=ch[i]-'0';sum[1]=1;for(int i=2;i<=700;i++)sum[i]=(sum[i-1]*10+1)%mod;memset(f,-1,sizeof(f));LL ans=0;for(int i=1;i<=9;i++)for(int j=1;j<=len;j++)ad(ans,sum[j]*dp(len,j,i,1)%mod);printf("%lld\n",ans);return 0; }