HNOI2011 卡农

题目:

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

思路:

  啊计数题这辈子都写不来的qwq
  如果把集合转化成二进制,也就是要求取 个不同的数使得异或和为 。那么可以考虑用最后一个元素来把前面的异或和补成 ,那么这样的方案数就是 。但是这样是有一些不合法方案的,因为最后一个元素不能为 ,也不能和前面元素重复。
  如果设选 个的方案为 ,第 个为 的情况数是 ,第 个与前面重复的方案是 (选一个重复位置再选一个数值)。然后就只要 转移一下就行了。

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int MOD = 100000007, N = 1000005;
int qkpow(int x, int k) {
    int ans = 1;
    for(; k; k >>= 1, x = (ll) x * x % MOD)
        if(k & 1) ans = (ll) ans * x % MOD;
    return ans;
}
int inv(int a) {
    return qkpow(a, MOD - 2);
}

int dp[N], g[N];

int main() {
    File(canon);
    int n, m;
    scanf("%d%d", &n, &m);
    int all = qkpow(2, n) - 1;
    g[0] = dp[0] = 1;
    rep(i, 1, m) g[i] = (ll) g[i - 1] * (all - i + 1) % MOD;
    rep(i, 2, m) dp[i] = (g[i - 1] - dp[i - 1] - (ll) dp[i - 2] * (i - 1) % MOD * (all - i + 2)) % MOD;
    int fac = 1;
    rep(i, 1, m) fac = (ll) fac * i % MOD;
    dp[m] = (ll) dp[m] * inv(fac) % MOD;
    printf("%d\n", (dp[m] + MOD) % MOD);
    return 0;
}