Problem
Solution
首先对题意进行一步转换：从 ([1,2^n-1]) 中选出不重复的 (m) 的数，使它们的异或和为 (0) 的方案数。
手推一下即可。
为了计算方便，我们考虑顺序，最后再把顺序处理掉（即选择的集合相同，顺序不同视作不同的方案）。
设 (f[i]) 表示选择 (i) 个数异或之和为 (0) 的方案数。
由于条件异或之和为 (0)，故选择了 (i-1) 个数后，最后一个数也确定了。所以全集为 (A^{i-1}_{2^n-1})（其中包含了不合法的）。
考虑不合法的方案：
-
1.前 (i-1) 个数的异或和为 (0)，那么最后一个数自动选 (0)，由于 (0 otin [1,2^n-1])，故不合法。该情况的方案数是 (f[i-1])。
-
2.前 (i-1) 个数的异或和为 (x)，那么最后一个数自动选 (x)，且 (x in S)（令 (S) 为前 (i-1) 个数的集合），即出现重复的数字。实际上就是前 (i-2) 个数的异或和为 (0)，枚举最后选择的重复的数字，一共有 (2^n-1-(i-2)) 种选择的方案。注意我们考虑的是有顺序的，要考虑这个重复的数字放入任意一个位置，所以要再乘一个 (i-1)。所以该情况的方案数是 (f[i-2]*(2^n-1-(i-2))*(i-1))。
综上，可以得到：
[f[i] = A^{i-1}_{2^n-1} - (f[i-1] + f[i-2]*(2^n-1-(i-2))*(i-1))
]
边界 (f[1]=0,f[2]=0)。
由于我们考虑了顺序，那么处理掉顺序的影响，答案应该是 (frac{f[m]}{m!})。时间复杂度 (O(n))。
Code
Talk is cheap.Show me the code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
const int N = 1e6+7, mod = 1e8+7;
int n,m,pn;
int g[N],f[N];
int jc(int x) {
int res = 1;
for(int i=1;i<=x;++i) {
res = (res * i) % mod;
}
return res;
}
int Pow(int x,int y) {
int res = 1, base = x;
while(y) {
if(y&1) res = res*base%mod; base = base*base%mod; y >>= 1;
}
return res;
}
int Inv(int x) {
return Pow(x,mod-2);
}
void Init() {
pn = Pow(2,n);
g[0] = 1;
for(int i=1;i<=m;++i) g[i] = g[i-1] * ((pn-i + mod)%mod) % mod;
}
signed main()
{
n = read(), m = read();
Init();
for(int i=3;i<=m;++i) {
f[i] = (g[i-1] - (f[i-1] + f[i-2]*(((pn-1) - (i-2) + mod)%mod)%mod*(i-1)%mod)%mod + mod) % mod;
}
printf("%lld
",f[m]*Inv(jc(m))%mod);
return 0;
}
/*
2999 3000
94342341
*/
Summary
考虑一下问题的全集，不合法方案和合法方案。只用到补集算比较简单的容斥，主要是问题的转化这一步比较难。
多做题！