CF238
CF238A
CF238A题意
给出两个整数 \(n,m\)，现在问你有多少个序列 \(a\) 满足：
- 序列长度为 \(n\)。
- \(a_i\in[0,2^m-1]\)
- \(\forall 1\le i\le j \le n,a_i\oplus a_{i+1}\oplus\dots\oplus a_j\neq0\)
答案对 \(10^9+9\) 取模。
CF238A题解
不难想到转化题意，即设 \(s_i=\oplus_{j=1}^ia_j\)，那么题意转化为 \(\forall 0\le i< j \le n,s_i\oplus s_j\neq0\)。
然后发现这个相当于在 \([1,2^m-1]\) 中选不同的 \(n\) 个数。
然后就没了。
CF238A代码
#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 << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e5 + 10, mod = 1e9 + 9;
int n, m;
signed main(){
n = read(); m = read();int ans = 1, pw = 1;
for(int i = 1;i <= m;i++){pw = (pw * 2ll) % mod;}pw = (pw - 1 + mod) % mod;
for(int i = 0;i < n;i++){ans = ans * (pw - i + mod) % mod;}
printf("%lld\n",ans);
return 0;
}