The 2019 ICPC China Shaanxi Provincial Programming Contest A. Digit Mode（数位dp 计数 指数型生成函数 暴力dp）

题目

思路来源

乱搞ac

题解

本质是想知道已经选了ai个i，还有x个数可以随便选的时候，j是众数的方案数

枚举这个随便选的临界位i（也就是不卡上界的临界位），也就是[1,i-1]都是卡上界的，

枚举第i位选了什么，枚举此时对应的众数j，以及枚举j最后选了多少个

那对于其他位就有了一个上界的限制

其他位的方案数可以用指数生成函数求一下，

也就是求相同位视作相同球，不同位视作不同球的可重集全排列的方案数

针对上限是up的项，看成是一个的多项式

然后多项式卷积即可

此外，还有一种情况，是前面全选的前导0，从某一位开始才有数的，

那么情况类似，枚举有数的第一位i，也就是[1,i-1]都是全0

枚举第i位选了什么，枚举此时对应的众数j，以及枚举j最后选了多少个

那对于其他位就有了一个上界的限制，剩下的复用前半部分即可

众数是0时没有贡献，所以不用统计

由于范围比较小，所以卷积的部分可以暴力dp

复杂度大致是O(n*d*d*n*n*d)的，实际也跑不满，跑了600多ms

代码

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=55,M=10,mod=1e9+7;
int t,n,Finv[N],fac[N],inv[N],now[M],a[M],up[M],ans;
char s[N];
void add(int &x,int y){
    x=(x+y)%mod;
}
void init(int n){ //n<N
    inv[1]=1;
    for(int i=2;i<=n;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	fac[0]=Finv[0]=1;
	for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod,Finv[i]=1ll*Finv[i-1]*inv[i]%mod;
	//Finv[n]=modpow(fac[n],mod-2,mod);
	//for(int i=n-1;i>=1;--i)Finv[i]=1ll*Finv[i+1]*(i+1)%mod;
}
int C(int n,int m){
	if(m<0||m>n)return 0;
	return 1ll*fac[n]*Finv[n-m]%mod*Finv[m]%mod;
}
int sol(int x){
    if(!x)return 1;
    vector<int>dp(x+1,0);
    dp[0]=1;
    rep(i,0,9){
        auto ndp=dp;
        fill(ndp.begin(),ndp.end(),0);
        rep(j,0,x){
            rep(k,0,up[i]){
                if(j+k>x)break;
                add(ndp[j+k],1ll*dp[j]*Finv[k]%mod);
            }
        }
        dp=ndp;
    }
    return 1ll*dp[x]*fac[x]%mod;
}
int main(){
    init(N-2);
    sci(t);
    while(t--){
        ans=0;
        scanf("%s",s+1);
        memset(now,0,sizeof now);
        n=strlen(s+1);
        rep(i,1,n){//前缀均卡上界
            int ub=s[i]-'0';
            rep(j,0,ub){
                if(i==1 && j==0)continue;
                if(i<n && j==ub)continue;
                now[j]++;
                rep(k,1,9){
                    rep(l,1,n){
                        memcpy(a,now,sizeof now);
                        int v=l-a[k],left=n-i;
                        if(a[k]>l)continue;
                        if(a[k]+left<l)break;
                        a[k]+=v;
                        left-=v;
                        bool ok=1;
                        rep(x,0,9){
                            if(a[x]>a[k] || (x>k && a[x]==a[k]))ok=0;
                            else up[x]=l-a[x]-(x>k);
                        }
                        if(!ok)continue;
                        add(ans,1ll*C(n-i,v)*sol(left)%mod*k%mod);
                    }
                }
                now[j]--;
            }
            now[ub]++;
        }
        rep(i,2,n){//前缀均为0
            memset(now,0,sizeof now);
            rep(j,1,9){
                now[j]++;
                rep(k,1,9){
                    rep(l,1,n){
                        memcpy(a,now,sizeof now);
                        int v=l-a[k],left=n-i;
                        if(a[k]>l)continue;
                        if(a[k]+left<l)break;
                        a[k]+=v;
                        left-=v;
                        bool ok=1;
                        rep(x,0,9){
                            if(a[x]>a[k] || (x>k && a[x]==a[k]))ok=0;
                            else up[x]=l-a[x]-(x>k);
                        }
                        if(!ok)continue;
                        add(ans,1ll*C(n-i,v)*sol(left)%mod*k%mod);
                    }
                }
                now[j]--;
            }
        }
        pte(ans);
    }
    return 0;
}