CF908G New Year and Original Order

CF908G New Year and Original Order

gzz讲过，可我到今天还是不会

有点trick的数位DP

比较显然的思路是，考虑所有数中排序后每一位的贡献。cnt(i,x)表示S(1)~S(x)第i位是x的数的个数

设这个数大于x的出现j次，等于x的出现k次，充分必要条件是，j<i&&j+k>=i

所以f[i][j][k][x][0/1]前i位，j个>x，k个=x，有无限制

O(n^3*10^2)GG

讨厌的是，要记录j和k

恰好——>至少

dlt(i,x)第i位>=x的个数

充分必要条件是，>=x的出现>=i次

所以f[i][j][x][0/1]

O(n^2*10^2)

DP起来非常愉悦没有细节~

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
#define pb push_back
#define solid const auto &
#define enter cout<<endl
#define pii pair<int,int>
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}
template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');}
template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('
');}
namespace Modulo{
const int mod=1e9+7;
il int ad(int x,int y){return x+y>=mod?x+y-mod:x+y;}
il int sub(int x,int y){return ad(x,mod-y);}
il int mul(int x,int y){return (ll)x*y%mod;}
il void inc(int &x,int y){x=ad(x,y);}
il void inc2(int &x,int y){x=mul(x,y);}
il int qm(int x,int y=mod-2){int ret=1;while(y){if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}
template<class ...Args>il int ad(const int a,const int b,const Args &...args) {return ad(ad(a,b),args...);}
template<class ...Args>il int mul(const int a,const int b,const Args &...args) {return mul(mul(a,b),args...);}
}
using namespace Modulo;
namespace Miracle{
const int N=707;
char a[N];
int f[N][N][11][2];
int n;
int mi[N];
void dp(){
    for(reg i=1;i<=9;++i) f[n+1][0][i][1]=1;
    for(reg i=n;i>=1;--i){
        int c=(a[i]-'0');
        for(reg j=0;j<=n-i;++j){
            for(reg x=1;x<=9;++x){
                int v1=f[i+1][j][x][1],v0=f[i+1][j][x][0];
                if(v1){
                    for(reg p=0;p<c;++p){
                        inc(f[i][j+(p>=x)][x][0],v1);
                    }
                    inc(f[i][j+(c>=x)][x][1],v1);
                }
                if(v0){
                    for(reg p=0;p<=9;++p){
                        inc(f[i][j+(p>=x)][x][0],v0);
                    }
                }
            }
        }
    }
}
int dlt[N][11];
int main(){
    scanf("%s",a+1);
    n=strlen(a+1);
    reverse(a+1,a+n+1);
    dp();
    mi[0]=1;
    for(reg i=1;i<=n;++i) mi[i]=mul(mi[i-1],10);
    int ans=0;
    for(reg i=1;i<=n;++i){
        for(reg x=1;x<=9;++x){
            for(reg j=i;j<=n;++j){
                inc(dlt[i][x],ad(f[1][j][x][1],f[1][j][x][0]));
            }
        }
    }
    for(reg i=1;i<=n;++i){
        for(reg x=1;x<=9;++x){
            int tmp=sub(dlt[i][x],dlt[i][x+1]);
            inc(ans,mul(tmp,x,mi[i-1]));
        }
    }
    printf("%d",ans);
    return 0;
}

}
signed main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
*/

恰好——>至少，再差分

往往可以少记录很多东西，或者少转移很多东西！

前提是最后可以差分计算恰好的答案。