讲解 P9640 [SNCPC2019] Digit Mode。

使用数位 dp 算法，通过枚举众数和众数出现次数，然后使用动态规划算法结合组合数学计算贡献。

思路：

定义 \(F(l,r)\) 表示若已经确定了 \([1,l-1]\) 的数，且 \([l,r]\) 没有限制的贡献数。

设 \(n\) 的长度为 \(len\)，考虑先求出 \([1,i](i \le len-1)\) 的贡献（是没有限制的），那么每次枚举第 \(1\) 位数字 \(a_1 \in [1,9]\)，算上 \(F(2,i)\) 的贡献即可。

则该情况贡献和为：

\[\sum_{i=1}^{len-1} \sum_{j=1}^9 F(2,i)

\]

现在来考虑长度为 \(len\) 的数的贡献的和，也考虑枚举第 \(i\) 位的数字 \(j\)，那么若想要使得 \([i+1,len]\) 没有限制，则至少要满足 \(i \in [0,n_i-1]\)，为了使得后面不算重，故我们要每次算完 \([i+1,len]\) 的贡献和后，需要令 \(a_i = n_i\)。

则该情况贡献和为：

\[\sum_{i=1}^{len} \sum_{j=[i=1]}^{n_i-1} F(i+1,len)

\]

注意最后要单独计算 \(n\) 本身的贡献。

现在我们来考虑确定 \(a_{1,\cdots,l-1}\) 的情况下如何计算 \(F(l,r)\)。

考虑枚举众数最大值 \(i\) 和众数的出现次数 \(j\)，设 \(p_i\) 表示 \(i\) 的出现次数，那么在后面 \([l,r]\) 内 \(i\) 至少还需要出现 \(j-p_i\) 次；同时为了确保 \(i\) 是众数，需要满足 \([0,i-1]\) 的出现次数 \(\le j\)，且 \([i+1,9]\) 的出现次数 \(\le j-1\)；即现在我们要求将 \(r-l+1-(j-p_i)\) 个位置分配给除了 \(i\) 以外的 \(9\) 个数的且满足限制的方案数。

设我们枚举的众数为 \(k\)，众数出现次数为 \(mx\)，使用动态规划算法，定义 \(f_i\) 表示可以分配 \(i\) 个位置的方案数，考虑枚举选的数 \(j\) 和分配给 \(j\) 的数量 \(k\)，背包形转移：

\[f_i = \sum_{j=0}^9 [j \ne k] \sum_{k=0}^{\min(mx,p_j-[i>k])} \binom{i}{k} f_{i-k}

\]

可以先预处理阶乘和逆元来计算组合数。

注意要先枚举 \(j\)。

完整代码：

<code>#include<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#define fi first

#define se second

#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x

#define Full(a) memset(a,0,sizeof(a))

#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);

#define For(i,l,r) for(int i=l;i<=r;i++)

#define _For(i,l,r) for(int i=r;i>=l;i--)

using namespace std;

typedef long double lb;

typedef double db;

typedef unsigned long long ull;

typedef long long ll;

bool Begin;

const ll N=55,mod=1e9+7;

inline ll read(){

ll x=0,f=1;

char c=getchar();

while(c<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

ll T,n,t,g,ans,sum;

ll a[N],h[N],p[N],f[N],fac[N],inv[N];

char s[N];

ll qpow(ll a,ll b){

ll ans=1;

while(b){

if(b&1ll)

ans=(ans*a)%mod;

a=(a*a)%mod;

b>>=1ll;

}

return ans;

}

void init(){

fac[0]=fac[1]=1;

For(i,2,N-1)

fac[i]=(fac[i-1]*i)%mod;

inv[N-1]=qpow(fac[N-1],mod-2);

_For(i,0,N-2)

inv[i]=inv[i+1]*(i+1)%mod;

}

ll C(ll n,ll m){

if(m>n||m<0)

return 0;

if(!m||n==m)

return 1;

return fac[n]*inv[m]%mod*inv[n-m]%mod;

}

ll get(ll n,ll k,ll mx){

memset(f,0,sizeof(f));

f[0]=1;

For(i,0,9){

if(i==k)

continue;

t=mx-(i>k)-p[i];

if(t<0)

return 0;

_For(j,1,n)

For(k,1,min((int)t,j))

f[j]=(f[j]+f[j-k]*C(j,k)%mod)%mod;

}

return f[n];

}

ll get(ll l,ll r){

sum=0;

For(i,0,9)

p[i]=0;

For(i,1,l-1)

p[a[i]]++;

For(i,1,9)

For(j,p[i],p[i]+r-l+1)

sum=(sum+get(r-l+1-j+p[i],i,j)*C(r-l+1,r-l+1-j+p[i])%mod*i%mod)%mod;

return sum;

}

void solve(){

ans=0;

scanf("%s",s+1);

n=strlen(s+1);

For(i,1,n)

h[i]=s[i]-'0';

For(i,1,n-1){

For(j,1,9){

a[1]=j;

ans=(ans+get(2,i))%mod;

}

}

For(i,1,n){

For(j,(i==1),h[i]-1){

a[i]=j;

ans=(ans+get(i+1,n));

}

a[i]=h[i];

}

write((ans+get(n+1,n))%mod);

putchar('\n');

}

bool End;

int main(){

init();

T=read();

while(T--)

solve();

//cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";

return 0;

}