Link:
Solution:
其实就是利用数位$dp$的思想来暴力计数的一道题目
如果答案有$dgt$位,可以类似 [BZOJ 1833] 先计算出1至$dgt-1$位的情况再根据上界逐位枚举
不过实际上可以通过添补前导0的方式将所有情况都补为$dgt$位统一计算
其中组合数部分的计算可以使用阶乘的方式:$\frac{(\sum_{i=0}^9 cnt_i)!}{cnt_0!+cnt_1!…+cnt_9!}$
但为了防止阶乘爆$long long$,要通过拆分后统计每一个质因数个数的方式来求解
更简便的方式是直接使用组合数:$\sum_{i=0}^9 C[tot-sum(i-1)][cnt_i]$
Code:
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
ll res=;
char s[];
int C[][],cnt[],len;
int idx(char ch){return ch-'';}
int main()
{
C[][]=;
for(int i=;i<=;i++)
{
C[i][]=;
for(int j=;j<=;j++)
C[i][j]=C[i-][j-]+C[i-][j];
} scanf("%s",s+);len=strlen(s+);
for(int i=;i<=len;i++) cnt[idx(s[i])]++;
for(int i=;i<=len;i++)
{
for(int j=;j<idx(s[i]);j++)
if(cnt[j])
{
int t=len-i;ll pro=;
cnt[j]--;
for(int k=;k<=;k++)
pro*=C[t][cnt[k]],t-=cnt[k];
res+=pro;cnt[j]++;
}
cnt[idx(s[i])]--;
}
printf("%lld",res);
return ;
}
Review:
1、两阶乘相除位数不够时可以通过逐个质因数统计次幂的方式来解决
ll cal(ll x,ll t){
ll res=;
while (x/t) res+=(x/=t);
return res;
}
ll solve()
{
ll res=;
for (int i=;i<=tot && pri[i]<=mx;i++)
{
ll pw=cal(mx,pri[i]);
for (int j=;j<;j++) pw-=cal(cnt[j],pri[i]);
res=res*qpow(pri[i],pw);
}
return res;
}
2、通过添加前导零将所有答案化成同一位数,方便统计