HNOI2011卡农题解

发表于 | 更新于 | 分类于 ， ， ，

这大概是我第一道听懂了的容斥题了吧(入门那种不算)

题意描述

众所周知卡农是一种复调音乐的写作技法，小余在听卡农音乐时灵感大发，发明了一种新的音乐谱写规则。他将声音分成 n 个音阶，并将音乐分成若干个片段。音乐的每个片段都是由 1 到 n 个音阶构成的和声，即从 n 个音阶中挑选若干个音阶同时演奏出来。为了强调与卡农的不同，他规定任意两个片段所包含的音阶集合都不同。同时为了保持音乐的规律性，他还规定在一段音乐中每个音阶被奏响的次数为偶数。现在的问题是：小余想知道包含 m 个片段的音乐一共有多少种。两段音乐 a 和 b 同种当且仅当将 a 的片段重新排列后可以得到 b。例如：假设 a为(1,2),(2,3)，b 为(3,2),(2,1)，那么 a 与 b 就是同种音乐。由于种数很多，你只需要输出答案模 100000007（质数）的结果。

题意简述

有一个集:$S{1,2,3,\cdots,n}$让你在里面选择$m$个集合并且满足如下性质:

  • 不能为空集
  • 没有重复的集合
  • 每个元素的总出现次数必定为偶数次

分析一波

主要算法分析

首先我们可以很显然地知道不一定满足上述三个条件的所有情况:$A_{2^n}^{i}$但是这里我们也显然可以排除空集情况,变成:$A_{2^n -1}^{i}$那么我们既然可以知道所有的情况，也知道用来排除错误情况的条件,那么就显然容斥咯(说的自在,自己还不是没想出来)

算法实现分析

分析上述三点条件,发现第三条能够实现从选择了$i-1$个集合具体状态直接推导出选择了$i$个的状态

$f[i]:$选择i个集合的可能状态数

所以选i个的状态数被排除到了$A_{2^n -1}^{i-1}$

那么再用条件1推导:发现如果要当前选择集合为空集,那么前i-1个就一定能够组成一个合法状态,所以,条件1又排除掉了$f[i-1]$个状态

最后再来看条件2:首先,假设第$i$(也就是当前选择的最后一个集合)和$j(j<i)$集合完全相同且这个状态除了这个问题没有违反任何条件,那么显然去掉集合$i$与集合$j$剩下的i-2个集合能够组成一个符合条件的状态,而$j$有$i-1$个位置可选,以及$2^n -1-(i-2)$个集合可选而去掉$i$和$j$之后符合条件的状态数为$f[i-2]$,按照乘法原理,我们又排除了$f[i-2]\cdot(i-1)\cdot (2^n -1-(i-2))$个状态

so?!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<bitset>
#include<map>
#include<set>
#define ll long long
#define db double
#define mod 100000007
#define maxn 1000005
using namespace std;
ll max(ll a,ll b){if(a>b)return a;return b;}
ll min(ll a,ll b){if(a<b)return a;return b;}
ll read(){
	ll ans=0,fh=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')fh=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		ans=ans*10+c-'0';
		c=getchar();
	}
	return ans*fh;
}
ll n,m,f[maxn],MX=1,A[maxn],qwq;
ll Pow(ll x,ll y,ll p){
	ll ret=1;
	while(y){
		if(y&1)(ret*=x)%=p;
		(x*=x)%=p;
		y>>=1;
	}
	return ret%mod;
}
int main(){
	n=read();m=read();
	if(m==1||m==2){puts("0");return 0;}
	f[1]=0;f[2]=0;
	A[0]=1;qwq=1;
	for(int i=1;i<=n;i++)(qwq*=2)%=mod;
	for(int i=1;i<=m;i++){
		A[i]=A[i-1]*(qwq-i)%mod;
	}
	for(int i=3;i<=m;i++){
		f[i]=(A[i-1]-f[i-1]+mod-f[i-2]*(i-1)%mod*(qwq-i+1)%mod+mod)%mod;
	}
	for(int i=1;i<=m;i++)(MX*=i)%=mod;
	cout<<f[m]*Pow(MX,mod-2,mod)%mod;
	return 0;
}

完结撒花！