洛谷P2606 [ZJOI2010]排列计数 题解
题目链接:P2606 [ZJOI2010]排列计数
题意:
称一个 $1 \sim n$ 的排列 $p_1,p_2, \dots ,p_n$ 是 Magic 的,当且仅当
计算 $1 \sim n$ 的排列中有多少是 Magic 的,答案可能很大,只能输出模 $m$ 以后的值。
对于 $100\%$ 的数据,$1\le n \le 10^6,~1\le m \le 10^9$,$m$ 是一个质数。
给张图。
题目就是问 $n$ 个结点的完全二叉树有多少种满足小根堆性质
设 $f_i$ 表示以 $i$ 为根的子树的答案, $s_i$ 表示原树中以 $i$ 为根的子树有多少个结点
考虑转移。根一定要放这个子树中最小的,其他的就挑 $s_{2i}$ 个放左子树就好了,则
因为没有保证 $n<m$ ,因此考虑Lucas定理
时间复杂度 $O(\epsilon n \log n)$,$\epsilon = \log_m{n}$
代码:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e6+15))
int n,mod,sz[N<<1],f[N<<1],fac[N];
int mul(int cnt, ...)
{
va_list ptr; va_start(ptr,cnt);
int res=1;
for(int i=0; i<cnt; i++)
res=res*va_arg(ptr,int)%mod;
va_end(ptr);
return res;
}
int qpow(int a,int b)
{
int ans=1,base=a%mod;
for(; b; b>>=1)
{
if(b&1) ans=ans*base%mod;
base=base*base%mod;
}
return ans;
}
int C(int n,int m)
{
if(n<m)return 0;
return mul(3,fac[n], qpow(fac[m],mod-2), qpow(fac[n-m],mod-2));
}
int lucas(int n,int m)
{
if(!m)return 1;
return lucas(n/mod, m/mod) * C(n%mod, m%mod) % mod;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> mod; fac[0]=1;
for(int i=1; i<=n; i++) fac[i] = fac[i-1] * i % mod;
for(int i=1; i<=n; i++) sz[i]=1;
for(int i=n; i>=2; i--) sz[i>>1] += sz[i];
for(int i=n+1; i<=n*2+1; i++) f[i]=1;
for(int i=n; i; i--) f[i] = mul(3, f[i<<1], f[i<<1|1], lucas(sz[i]-1,sz[i<<1]));
cout << f[1] << '\n';
return 0;
}