【CF908G】New Year and Original Order（动态规划）

题面

题解

设(f[i][j][k][0/1])表示当前填到了第(i)位，有(j)个大于等于(k)的数，是否卡到上界的方案数。
这个东西算完之后，等价于默认排好序了。
看起来可以枚举每个数字出现在第几位了。
然而实际上不知道这个数字的出现次数，所以不能按照(10^j*k)这样子计算贡献。
怎么办呢，假设前面有(j)个数大于(k)的数，那么就产生(sum_{i=0}^{j-1}10^i)的贡献。
把样例蒯下来手玩一下就知道为啥是对的了。
(3459)：(ge 3)的有(4)个，(ge 4)的有(3)个，(ge 5)的有(2)个，(ge 6..8)的有(2)个，(ge 9)的有(1)个。
所以贡献就是(1111*3+111*4+11*1+11*3+1*9=3456)。
本质上是考虑把(k*10^i)拆成(k)个(10^i)的和的形式。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MOD 1000000007
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
int n,ans;char s[705];
int f[705][705][10][2];
int main()
{
	scanf("%s",s+1);n=strlen(s+1);
	for(int i=0;i<=9;++i)f[0][0][i][0]=1;
	for(int i=1;i<=n;++i)
		for(int j=0;j<=i;++j)
			for(int k=0;k<=9;++k)
				for(int l=0;l<=1;++l)
					for(int p=0,lim=l?9:s[i]-48;p<=lim;++p)
						add(f[i][j+(k<=p)][k][l|(p<lim)],f[i-1][j][k][l]);
	for(int k=1;k<=9;++k)
		for(int j=1,v=1;j<=n;++j,v=(10ll*v+1)%MOD)
			add(ans,1ll*v*(f[n][j][k][0]+f[n][j][k][1])%MOD);
	printf("%d
",ans);return 0;
}