bzoj4980: 第一题

时间：2021-12-22 05:05:04

Description

神犇xzyo听说sl很弱，于是出了一题来虐一虐sl。一个长度为2n（可能有前缀0)的非负整数x是good的，当且仅当
存在两个长度为n（可能有前缀0）的非负整数a、b满足a+b==10n，并且对于0~9每个数位d，都有Sd(x)==Sd(a)+Sd(
b)(Sd(x)为x的十进制中d出现了多少次)。例如0829是good的，98+02==100。给出一个长度为2n的序列，其中有些
位置是问号。将每个问号替换为0~9任意一个数位后，有多少个good数，答案对1000000007取膜。为了sl不被虐死
，快告诉他怎么写吧。
两个数相加为10^n，意味着可以将数位一部分按09,18,27,36,45配对表示较高位的情况，低位有一对19,28,37,46,55产生了一次进位，更低位可以全0。枚举哪一对数产生进位，可以算出0的出现次数-9的出现次数，1-8，2-7，3-6，4-5的值，然后做一次背包。需要特判一些情况：因为两个0可以配对，0-9的值表示的是0至少比9多几个，实际可以再把一些9换成0，但如果19产生进位，必须留下至少一个9（可能来自已确定的数位，也可能必须由?提供）而不能全部换成0。
#include<bits/stdc++.h>

typedef long long i64;

const int P=1e9+;

char s[];

int n,t[],m=,ts[];

i64 f[],g[],fac[],fiv[],ans=;

i64 _ks[][],(*ks)[]=_ks+;

bool d9=;

void cal(int tp){

    memset(f,,sizeof(f));

    f[]=;

    for(int i=;i<;++i){

        memset(g,,sizeof(g));

        if(ts[i]>m||i&&ts[i]<-m)return;

        if(!i){

            while(ts[i]<-m)ts[i]+=;

            for(int s=,d=;s<=m;++s){

                i64 iv=ks[ts[i]][s];

                if(!iv)continue;

                if(tp==&&!d9&&(s+ts[i])%==)iv=(iv-fiv[s]+P)%P;

                for(int j=s;j<=m;++j)g[j]+=f[j-s]*iv;

                if(++d>){

                    d=;

                    for(int j=;j<=m;++j)g[j]%=P;

                }

            }

        }else for(int a=ts[i],b=,d=;a+b<=m;++a,++b)if(a>=){

            int s=a+b;

            i64 iv=fiv[a]*fiv[b]%P;

            for(int j=s;j<=m;++j)g[j]+=f[j-s]*iv;

            if(++d>){

                d=;

                for(int j=;j<=m;++j)g[j]%=P;

            }

        }

        for(int j=;j<=m;++j)f[j]=g[j]%P;

    }

    ans=(ans+f[m]*fac[m])%P;

}

i64 pw(i64 a,int n){

    i64 v=;

    for(;n;n>>=,a=a*a%P)if(n&)v=v*a%P;

    return v;

}

int main(){

    for(int i=fac[]=;i<=;++i)fac[i]=i*fac[i-]%P;

    fiv[]=pw(fac[],P-);

    for(int i=;i;--i)fiv[i-]=i*fiv[i]%P;

    scanf("%s",s);

    n=strlen(s);

    if(n&)return puts(""),;

    for(int i=;i<n;++i){

        if(s[i]=='?')++m;

        else ++t[s[i]-''];

        d9|=s[i]=='';

    }

    for(int i=m;i>=-m;--i){

        for(int a=i,b=;a+b<=m;++a,++b)if(a>=)ks[i][a+b]=fiv[a]*fiv[b]%P;

        for(int j=;j<=m;++j)ks[i][j]=(ks[i][j]+ks[i+][j])%P;

    }

    for(int i=;i<=;++i){

        for(int j=;j<;++j)ts[j]=t[j];

        --ts[i],--ts[-i];

        for(int j=;j<;++j)ts[j]=ts[-j]-ts[j];

        i64 a0=ans;

        cal(i);

        a0=ans-a0;

    }

    printf("%lld\n",ans);

    return ;

}

相关文章