首页 > 代码库 > BZOJ 2339[HNOI2011]卡农
BZOJ 2339[HNOI2011]卡农
题面：
2339: [HNOI2011]卡农
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 807 Solved: 483
[Submit][Status][Discuss]
Description
令f[i]为前i个集合满足条件的方案数,则前i-1个集合确定后,第i个也随之确定(元素出现偶数次)。
f[i]=A[m][i-1]-f[i-1](前i-1个集合已经满足元素出现偶数次)-f[i-2]*(i-1)*(2^n-1-i+2)(第i个集合在前i-1个集合中出现过)
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 using namespace std; 6 #define maxn 1000001 7 #define mod 100000007 8 #define LL long long 9 LL f[maxn],g[maxn];10 LL mx;11 int n,m;12 LL qpow(LL x,LL y)13 {14 LL ans=1;15 for(;y;y>>=1,x=x*x%mod)16 if(y&1)17 ans=ans*x%mod;18 return ans;19 }20 void init()21 {22 mx=qpow(2,n);23 mx=--mx;24 g[0]=1;25 for(int i=1;i<=m;i++)26 g[i]=g[i-1]*(mx-i+1)%mod;27 }28 void dp()29 {30 init();31 for(int i=3;i<=m;i++)32 {33 f[i]=g[i-1]+(mod-f[i-1])+(mod-f[i-2]*(i-1)%mod*(mx-(i-2)+mod)%mod);34 f[i]%=mod;35 }36 }37 int main()38 {39 scanf("%d%d",&n,&m);40 dp();41 LL s=1;42 for(int i=2;i<=m;i++)43 s=s*i%mod;44 printf("%d",f[m]*qpow(s,mod-2)%mod);45 }
BZOJ 2339[HNOI2011]卡农
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。