从 $[1,2^n)$ 中选择 $m$ 个互不相同且异或和为 $0$ 的数，求方案数。
$1 \le n,m \le 10^6$。
考虑 DP，记 $f_i$ 为选择 $i$ 个数的方案数。先考虑顺序，这样选择的数不会有顺序的限制，最后再除 m! 得到答案。
发现确定前 $i-1$ 个数就可以通过异或和为 $0$ 的条件得到第 $i$ 个数，那么得到初始方案数 $\binom{2^n-1}{i-1}(i-1)!$。记前 $i-1$ 个数的异或和为 $u$，那么 $i$ 填 $u$。考虑不合法的方案，减去 $u=0$ 和 $u$ 出现两次的方案，剩下的都合法。得到转移式
初值 $f_1=f_2=0$。时间复杂度 $O(m)$。
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,MOD=1e8+7;
inline int qm(int x,int y=MOD-2){ int res=1; for(;y;y>>=1,x=1ll*x*x%MOD) if(y&1) res=1ll*res*x%MOD; return res; }
inline void mod(int &x){ if(x>=MOD) x-=MOD; if(x<0) x+=MOD; }
#define gc getchar()
#define rd read()
inline int read(){
int x=0,f=0; char c=gc;
for(;c<'0'||c>'9';c=gc) f|=(c=='-');
for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
int jc[N],fjc[N];
void init(int n){
jc[0]=1; for(int i=1;i<=n;++i) jc[i]=1ll*jc[i-1]*i%MOD;
fjc[n]=qm(jc[n]); for(int i=n-1;~i;--i) fjc[i]=1ll*fjc[i+1]*(i+1)%MOD;
}
int n,m,pw,A[N],f[N];
int main(){
n=rd,m=rd,pw=qm(2,n),init(m);
for(int i=A[0]=1;i<=m;++i) A[i]=1ll*A[i-1]*(pw-i)%MOD;
f[1]=f[2]=0;
for(int i=3;i<=m;++i){
mod(f[i]=A[i-1]-f[i-1]);
mod(f[i]-=1ll*(pw-1-(i-2))*(i-1)%MOD*f[i-2]%MOD);
}
printf("%d\n", 1ll*f[m]*fjc[m]%MOD);
return 0;
}
|