题解 P2606 【[ZJOI2010]排列计数】

· · 题解

一个很妙的做法

观察题目发现答案等价于求一个树的拓扑排序数量。

所以可以直接套公式 ans=\frac{n!}{\prod ^ n_{i=1}s[i]}

这道题就做好了！！！

还是说公式的事

已知 f[u]=\frac{(s[u]-1)!*\prod f[v]!}{\prod s[v]!} (v是u的儿子)

设 g[u]=\frac{f[u]}{s[u]!}

可以得到 g[u]=\frac{\prod g[v]}{s[u]}=\frac{1}{\prod s[k]} (k是以u为根的子树上的点)

所以 g[1]=\frac{1}{\prod ^ n_{i=1}s[i]},ans=f[1]=g[1]*s[1]!=\frac{n!}{\prod ^ n_{i=1}s[i]}

得证

贴上简短的代码

#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
#define mn 1000005
ll n,p,s[mn],ans=1,i,inv[mn];
int main()
{
    scanf("%lld%lld",&n,&p);
    inv[1]=inv[0]=1;
    for(i=1;i<=n;i++)   s[i]=1;
    for(i=2;i<=n;i++)   inv[i]=(p-p/i)*inv[p%i]%p;//线性求逆元
    for(i=n;i>=2;i--)   s[i>>1]+=s[i];//统计s[i]
    for(i=1;i<=n;i++)   ans=ans*i%p*inv[s[i]]%p;//求答案
    printf("%lld",ans);
    return 0;
}