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

题面

洛谷
CF

题解

设\(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\n",ans);return 0; }

转载于:https://www.cnblogs.com/cjyyb/p/10473938.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/97713181

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。