CF908G New Year and Original Order

CodeForces

Luogu翻译

分析

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

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

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

$f[i][j+(p>=k)][k][l||(p<a[i])]=\sum f[i-1][j][k][l]$

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

实际上前$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$统计即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MOD=1e9+7;

char s[710];
int a[710];
int f[710][710][10][2]; //f[i][j][k][0/1]表示前i位有j位的数字大于等于k,是否小于n的方案数

inline void pls(int& x,int y) { x+=y; if (x>=MOD) x-=MOD; }

int main() {
    scanf("%s",s+1); int n=strlen(s+1);
    for (re int i=1;i<=n;++i) a[i]=s[i]-'0';
    for (re int i=0;i<=9;++i) f[0][0][i][0]=1;
    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)
                        pls(f[i][j+(p>=k)][k][l||(p<a[i])],f[i-1][j][k][l]);
    int ans=0;
    for (re int k=1;k<=9;++k)
        for (re int i=1,p=1;i<=n;++i,p=(10ll*p+1)%MOD)
            pls(ans,1ll*p*(f[n][i][k][0]+f[n][i][k][1])%MOD);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 56 PM

发表评论