【CF908G】New Year and Original Order
题面
题解
设\(f[i][j][k][l]\)表示当前在第\(i\)位有\(j\)位大于等于\(k\)，当前有没有卡上界的方案数
则枚举新加的数\(p\)，有
\[f[i+1][j+(p\geq k)][k][l|(p<a_i)]=\sum f[i][j][k][l]
\]
\]
我们最后统计答案的时候枚举\(k\)
有
\[ans=\underbrace{111...11}_{j个1}*(f[i][j][k][0]+f[i][j][k][1])
\]
\]
为什么要乘那么多\(1\)呢？(下面是张图片)
代码(压行有点丑)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define rep(i, from, to) for(int i = (from); i <= (to); i++)
const int Mod = 1e9 + 7;
const int MAX_N = 1005;
void pls(int &x, int y) { x += y; if (x >= Mod) x -= Mod; }
char ch[MAX_N]; int a[MAX_N], N;
int ans, f[MAX_N][MAX_N][10][2];
int main () {
scanf("%s", ch + 1); N = strlen(ch + 1);
rep(i, 1, N) a[i] = ch[i] - '0';
rep(i, 0, 9) f[0][0][i][0] = 1;
rep(i, 0, N - 1) rep(j, 0, i) rep(k, 1, 9) rep(l, 0, 1) rep(p, 0, (l ? 9 : a[i + 1]))
pls(f[i + 1][j + (p >= k)][k][l | (p < a[i + 1])], f[i][j][k][l]);
rep(k, 1, 9) {
int res = 1;
rep(i, 1, N) pls(ans, 1ll * res * (f[N][i][k][0] + f[N][i][k][1]) % Mod), res = (10ll * res + 1) % Mod;
}
printf("%d\n", ans);
return 0;
}