题意
给定正整数 \(n,m\),你需要从 \(\{1,2,\cdots n\}\) 集合中选出 \(m\) 个互不相等的非空子集,并且 \(1\sim n\) 的每个元素都在选出的集合中总共出现了偶数次。求选择的方案数对 \(10^8+7\) 取模的结果。
题解
题意等价于你需要选择 \(m\) 个 \(n\) 位二进制数,满足
- 数字都不为 \(0\);
- \(m\) 个数字互不相同;
- \(m\) 个数字的异或和为 \(0\);
记值域大小 \(k=2^n-1\)。
显然我们可以钦定 \(m\) 个子集组成的序列有序,然后将最终结果除以 \(m!\)。我们注意到,由于异或和为 \(0\) 的限制,选择了前 \(m-1\) 个元素之后,第 \(m\) 个元素就唯一确定了。现在我们尝试去掉重复和空的方案。
设 \(f_i\) 表示 \(m=i\) 时的答案。前 \(i-1\) 个元素的总方案数为 \(\binom{k}{i-1}\),此时第 \(i\) 个元素已经唯一确定为前面数字的异或和。
尝试去掉不满足 \(1\) 的方案数,容易发现,当 \(a_i=0\) 当且仅当前 \(i-1\) 个数字构成一组异或和为 \(0\) 的合法方案,因此方案数为 \(f_{i-1}\)。
尝试去掉不满足 \(2\) 的方案数,由于前 \(i-1\) 个数字都互不相等,因此考虑 \(a_i\) 和前面的 \(a_j\) 相等的情况。当我们固定 \(j\) 之后,剩下的 \(i-2\) 个数又构成一组合法方案,方案数为 \(f_{i-2}\)。同时,\(j\) 有 \(i-1\) 种不同的取值,\(a_i\) 和 \(a_j\) 有 \(k-i+2\) 种不同的取值,都和另外 \(i-2\) 个数的方案独立,因此总方案数为 \((i-1)(k-i+2)f_{i-2}\)。
因此,转移如下:
\[
f_i=\binom{k}{i-1}-f_{i-1}-(i-1)(k-i+2)f_{i-2}
\]
时间复杂度 \(O(m)\)。
AC 代码
| #include<iostream>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
const int MOD = 1e8 + 7;
int n, m, k;
int inv[N], fact[N], chs[N];
int f[N], ans;
inline int qpow(int a, int b) {
int res = 1;
while(b) {
if(b & 1) res = (ll)res * a % MOD;
a = (ll)a * a % MOD;
b >>= 1;
}
return res;
}
int main() {
cin >> n >> m;
k = qpow(2, n) - 1;
fact[0] = inv[1] = chs[0] = 1;
for(int i = 1; i <= m; i++) fact[i] = (ll)fact[i - 1] * i % MOD;
for(int i = 2; i <= m; i++) inv[i] = MOD - (ll)(MOD / i) * inv[MOD % i] % MOD;
for(int i = 1; i <= m; i++) chs[i] = (ll)chs[i - 1] * (k - i + 1) % MOD * inv[i] % MOD;
f[0] = 1;
f[1] = 0;
for(int i = 2; i <= m; i++) {
f[i] = (ll)chs[i - 1] * fact[i - 1] % MOD - f[i - 1] - (ll)f[i - 2] * (i - 1) % MOD * (k - i + 2) % MOD + 2 * MOD;
f[i] %= MOD;
}
ans = f[m];
for(int i = 1; i <= m; i++) ans = (ll)ans * inv[i] % MOD;
cout << ans << '\n';
return 0;
}
|