首页 > 代码库 > BZOJ 2111 排列计数
BZOJ 2111 排列计数
f[i]=f[l]*f[r]*C(size[l]+size[r],size[l]).
需要lucas.
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1000050 using namespace std; long long n,mod,inv1[maxn],inv2[maxn],f[maxn],size[maxn]; long long f_pow(long long x,long long y) { long long ans=1,base=x; while (y) { if (y&1) ans=(ans*base)%mod; base=(base*base)%mod; y>>=1; } return ans; } void get_table() { inv1[0]=1;inv2[0]=mod+1; for (long long i=1;i<=n;i++) { inv1[i]=inv1[i-1]*i%mod; inv2[i]=f_pow(inv1[i],mod-2); } } long long comb(long long n,long long m) { return inv1[n]*inv2[m]%mod*inv2[n-m]%mod; } long long lucas(long long n,long long m) { if (!m) return 1; return comb(n%mod,m%mod)*lucas(n/mod,m/mod)%mod; } int main() { scanf("%lld%lld",&n,&mod); get_table(); for (long long i=n;i>=1;i--) { size[i]=1;long long l=0,r=0;f[i]=1; if ((i<<1)<=n) {size[i]+=size[i<<1];l=size[i<<1];f[i]=f[i]*f[i<<1]%mod;} if ((i<<1|1)<=n) {size[i]+=size[i<<1|1];r=size[i<<1|1];f[i]=f[i]*f[i<<1|1]%mod;} f[i]=f[i]*lucas(l+r,l)%mod; } printf("%lld\n",f[1]%mod); return 0; }
BZOJ 2111 排列计数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。