CF908G解题报告 题意 题解 Code
定义(S(n))为将(n)的每一位数字升序排序后的值,例如:
[S(1)=1,S(5)=5,S(50394)=S(3459),S(353535)=333555
]
计算(sum_{i=1}^XS(i) mod 10^9+7)。
题解
考虑每一位的贡献可以表示成(c(digit)=sum10^i)的形式,那么通过更改求和顺序我们可以得到:(Ans=sum_{digit=1}^9digit*c(digit)=sum_{digit=1}^9sum_{i=digit}^9c(i))。
考虑枚举(digit)如何计算(sum_{i=digit}^9c(i)),它的意义是每个数中不小于(digit)的数位有多少个。
那么我们可以得到如下数位(dp):
[egin{align}
状态设计:&f[i][j][0/1]表示前i位中有j位的值大于等于枚举的dig,前i位小于(0)/等于(1)给定数的前i位\
init:&f[0][0][1]=1\
tran:&f[i][j][0]=sum_{0leq dleq9}f[i-1][j-(dgeq dig)][0]+sum_{0leq d< s[i]}f[i-1][j-(d>=dig)][0]\
&f[i][j][1]=f[i-1][j-(s[i]geq dig)][1]\
Ans:&sum_{1leq ileq n}f[n][i][0]
end{align}
]
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 750, mod = 1e9 + 7;
int n, f[N][N][2], ans, pw[N];
char s[N];
void upd(int &x, int v) {(x += v) >= mod ? x -= mod : 0;}
int calc(int dig) {
memset(f, 0, sizeof(f));
f[0][0][1] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= n; j++) {
if(j - (s[i] >= dig) >= 0) f[i][j][1] = f[i - 1][j - (s[i] >= dig)][1];
for(int d = 0; d <= 9; d++) if(j - (d >= dig) >= 0) upd(f[i][j][0], f[i - 1][j - (d >= dig)][0]);
for(int d = 0; d < s[i]; d++) if(j - (d >= dig) >= 0) upd(f[i][j][0], f[i - 1][j - (d >= dig)][1]);
// printf("dig:%d f[%d,%d,0]=%d f[%d,%d,1]=%d
", dig, i, j, f[i][j][0], i, j, f[i][j][1]);
}
}
int ret = 0;
for(int i = 1; i <= n; i++) upd(ret, 1ll * f[n][i][0] * pw[i] % mod);
// printf("%d
", ret);
return ret;
}
int main() {
scanf("%s", s + 1); n = strlen(s + 1);
for(int i = 1; i <= n; i++) pw[i] = (1ll * pw[i - 1] * 10 + 1) % mod;
for(int i = n; i >= 1; i--) if(s[i] == '9') s[i] = '0'; else {s[i]++; break;}
for(int i = 1; i <= n; i++) s[i] -= '0';
for(int dig = 1; dig <= 9; dig++) upd(ans, calc(dig));
printf("%d
", ans);
return 0;
}