题解：P9640 [SNCPC2019] Digit Mode

· · 题解

思路

定义 a_i 为 n 在十进制中从高到低的第 i 位，n 一共有 cnt 位，b_i 为最终数在十进制中从高到低的第 i 位。

首先类似数位 DP，枚举有 x 位是填满的（对于每个 i\in[1,x]，满足 b_i=a_i），然后第 x+1 位满足 b_i<a_i，那么 x+2\sim cnt 位是可以随便填的。对于有前导零的情况，枚举前 x 位是 0，第 x+1 位必须填一个正整数，x+2\sim cnt 位也是可以随便填的。我们设已经确定下来的有效数位中 i 的出现次数为 add_i，可以随便填的数位个数为 len。

这时我们枚举出现次数最多的数是 m，其出现次数位 c，不难发现，对于 x\neq m，在随便填的位置中最多出现 lim_x=c-add_x-[x>c] 次，其实这很像多重背包。设 f_{i,j} 表示前 i 个数（不包括 m），一共用了 j 个数的方案数，则有转移：

f_{i,j}=\sum\limits_{k=0}^{k\le lim_i} f_{i-1,j-k}\times \binom{j}{k}

而最终对答案的贡献为 f_{9,len-(c-add_m)}\times\binom{len}{c-add_m}\times c。按上述方法转移即可。

最终复杂度为 O(cnt^4V^3)，其中 V 为数码的个数，看似很大，但是常数极小，可以通过。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9+7,N = 100;
int a[N],C[N][N],f[N],cnt,add[N],ans;
string s;
inline void work(int len)
{
    for(int c = 0;c<=9;c++) for(int m = add[c];m<=add[c]+len;m++)
    {
        int tot = len-(m-add[c]);
        for(int i = 0;i<=tot;i++) f[i] = 0;
        f[0] = 1;
        bool fl = 1;
        for(int i = 0;i<=9;i++)
        {
            if(i==c) continue;
            int lim = m-add[i];
            if(i>c) lim--;
            if(lim<0)
            {
                fl = 0;
                break;
            }
            for(int j = tot;j;j--)
                for(int k = 1;k<=min(lim,k);k++)
                    (f[j]+=f[j-k]*C[j][k])%=mod;
        }
        if(fl) (ans+=f[tot]*c*C[len][m-add[c]])%=mod;
    }
}
inline void solve()
{
    cin>>s,cnt = s.size();
    for(int i = 1;i<=cnt;i++)
        a[i] = s[i-1]-'0';
    for(int i = 0;i<=9;i++) add[i] = 0;
    for(int i = 1;i<=cnt;i++)
        add[a[i]]++;
    ans = 9;
    for(int i = 8;~i;i--)
        if(add[i]>add[ans]) ans = i;
    for(int i = 0;i<=9;i++) add[i] = 0;
    for(int i = 1;i<cnt;i++)
    {
        for(int j = 1;j<=9;j++)
            add[j]++,work(i-1),add[j]--;
    }
    for(int i = 1;i<=cnt;i++)
    {
        int mn = 1;
        if(i!=1) mn = 0; 
        for(int j = mn;j<a[i];j++)
            add[j]++,work(cnt-i),add[j]--;
        add[a[i]]++;
    }
    cout<<ans<<'\n';
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    C[0][0] = 1;
    for(int i = 1;i<N;i++)
    {
        C[i][0] = 1;
        for(int j = 1;j<=i;j++)
            C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
    }
    int T;cin>>T;
    while(T--) solve(); 
    return 0;
}