题解 CF908G 【New Year and Original Order】

2019-01-07 07:56:17


orz Kelin


$10^{700}$ 显然是数位DP。

设 $f[i][j][k][0/1]$ 表示前i位中有j位的数字大于等于k,是否小于n的方案数。

然后枚举第 $i$ 位的数字 $p$ ,直接大力转移。

for (re int i=1;i<=n;++i)
    for (re int j=0;j<i;++j)
        for (re int k=1;k<=9;++k)
            for (re int l=0;l<=1;++l)
                for (re int p=0;p<=(l?9:a[i]);++p)
                    add(f[i][j+(p>=k)][k][l||(p<a[i])],f[i-1][j][k][l]);

(add是加法+取模。)

边界是 $f[0][0][i][0]=1$ 。

再考虑一下怎么计算答案。

实际上前 $n$ 位有 $i$ 位数字大于等于 $k$ 的方案数 $s=f[n][i][k][0]+f[n][i][k][1]$ 。

每一个 $s$ 对 $ans$ 的贡献是 $sum\times\underbrace{111\cdots11}_{j\text{个}1}$

直接枚举 $i$ 和 $k$ 统计即可。

代码见blog