P2518 [HAOI2010] 计数 题解
DengDuck
·
·
题解
数位 DP？高精度？太神秘啦！是时候换个写法，__int128 薄纱全场！
较小的数字形态显然是一段相同的前缀，一个小于原数字的位置，后面随便放，随便放的排列数为：
\frac {(\sum\limits_{i=0}^9 cnt_i)!}{\prod\limits_{i=0}^9 (cnt_i!)}
这时候题解区似乎为了求这个东西弄出了很多神秘的算法，但是，我们完全可以用一个非常简单的思路！弄一个很大的质数当模数！然后直接算答案！
要多大？答案小于 $2^{63}-1$，小粉兔推荐了一个神秘的网站叫做 [WolframAlpha](https://m.wolframalpha.com/)，生成了一个大于这个值质数，是 $9223372036854775837$，在模意义下，直接求阶乘逆元来解决除法即可。
什么紫题？赶紧降红！
```cpp
#include<bits/stdc++.h>
#define LL long long
#define LF long double
#define pLL pair<LL,LL>
#define pb push_back
//#define fir first
//#define sec second
using namespace std;
//const LL inf;
const LL N=55;
const LL M=50;
__int128 mod,fac[N],inv[N],ans;
//const LF eps;
//const LL P;
__int128 ksm(__int128 x,__int128 y)
{
__int128 ans=1;
while(y)
{
if(y&1)ans=ans*x%mod;
x=x*x%mod,y>>=1;
}
return ans;
}
char c[N];
LL n,a[N],b[N];
void print(__int128 x)
{
if(x>9)print(x/10);
putchar(x%10+'0');
}
int main()
{
mod=9223372036854;
mod*=1000000;
mod+=775837;
fac[0]=1;
for(int i=1;i<=M;i++)fac[i]=fac[i-1]*i%mod;
inv[M]=ksm(fac[M],mod-2);
for(int i=M-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
scanf("%s",c+1);
n=strlen(c+1);
for(int i=1;i<=n;i++)
{
a[i]=c[i]-'0';
b[a[i]]++;
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=a[i]-1;j++)
{
if(!b[j])continue;
b[j]--;
LL s=0;
__int128 cnt=1;
for(int k=0;k<=9;k++)s+=b[k];
cnt=fac[s];
for(int k=0;k<=9;k++)cnt=cnt*inv[b[k]]%mod;
b[j]++;
ans=(ans+cnt)%mod;
}
b[a[i]]--;
}
print(ans);
return 0;
}
//RP++
```