[ZJOI2010]排列计数

$[ZJOI2010]$排列计数 链接:https://www.luogu.com.cn/problem/P2606 题面:求满足$p_{i}>p_{i/2}(∀i∈[2,n])$的排列个数。 题解:考虑将限制转化成一棵树,如果我们将$i$向$i/2$连边,这道题目变成了树上排列计数的裸题。转化为了一个树后,限制便变为了儿子的权值大于父亲,令$dp_{i}$表示$i$的子树的排列个数,转移时需要用多重集的排列数合并,则 $dp_{i}=(sz_{x}-1)!\times\dfrac{1}{\prod_{t∈son(i)}^{}sz_{t}!}\prod_{t∈son(i)}^{}dp_{t}$ ``` #include #include using namespace std; long long sz[1000001],n,m,dp[1000001],fac[1000001],invfac[1000001]; void dfs(int x) { sz[x]=1; dp[x]=1; if (x*2<=n) { dfs(x*2); dp[x]=dp[x]*dp[x*2]%m; dp[x]=dp[x]*invfac[sz[x*2]]%m; sz[x]+=sz[x*2]; } if (x*2+1<=n) { dfs(x*2+1); dp[x]=dp[x]*dp[x*2+1]%m; dp[x]=dp[x]*invfac[sz[x*2+1]]%m; sz[x]+=sz[x*2+1]; } dp[x]=dp[x]*fac[sz[x]-1]%m; return; } long long fast_pow(long long a,int b) { if (b==0) return 1; if (b&1) return fast_pow(a*a%m,b/2)*a%m; else return fast_pow(a*a%m,b/2); } int main() { cin>>n>>m; fac[0]=1; for (int i=1;i<=n;++i) fac[i]=fac[i-1]*i%m; invfac[n]=fast_pow(fac[n],m-2); for (int i=n-1;i>=0;--i) invfac[i]=invfac[i+1]*(i+1)%m; dfs(1); cout<