CF908G New Year and Original Order

题面

题意翻译

给定$n<=10^{700}$，问$1$到$n$中每个数在各数位排序后得到的数的和。答案$mod;10^9+7$。

题解

考虑设$f[i][j][k][0/1]$表示前$i$位有$j$位的数字大小$geq k$，是否严格小于$n$的方案数

转移时，枚举第$i+1$位填$p$

$$ f[i+1][j+(pgeq k)][k][l|(p < a_{i+1})]=sum f[i][j][k][l] $$

答案就是

$$ sum_ksum_j (f[n][j][k][0]+f[n][j][k][1]) imes underbrace{111cdots 11}_{j个1} $$

代码

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x))

const int maxn(710), Mod(1e9 + 7);
int n, ans, f[maxn][maxn][10][2], a[maxn];
char s[maxn];
inline int Add(int x, int y) { return (x + y) % Mod; }
inline void Plus(int &x, const int &y) { x = Add(x, y); }

int main()
{
	scanf("%s", s + 1); n = strlen(s + 1);
	for(RG int i = 1; i <= n; i++) a[i] = s[i] - '0';
	for(RG int i = 0; i < 10; i++) f[0][0][i][0] = 1;
	for(RG int i = 0; i < n; i++)
		for(RG int j = 0; j <= i; j++)
			for(int k = 1; k < 10; k++)
				for(int l = 0; l <= 1; l++)
					for(int p = 0; p <= (l ? 9 : a[i + 1]); p++)
						Plus(f[i + 1][j + (p >= k)][k][l | (p < a[i + 1])],
								f[i][j][k][l]);
	for(int k = 1; k < 10; k++)
	{
		int num = 1;
		for(RG int i = 1; i <= n; i++)
			Plus(ans, 1ll * num * (f[n][i][k][0] + f[n][i][k][1]) % Mod),
				num = (10ll * num % Mod + 1) % Mod;
	}
	printf("%d
", ans);
	return 0;
}