题面。
A.
不会线性基。
据说 lxl 一题多投（这题原来是学车的联赛模拟题，完了我连联赛水平都到不了了）。
好像会线性基这题就是显然了。
$i$ 前面能构成的数的个数就是 $2^{|P|}$。其中 $P$ 是线性基的基底。
然后就是把这些东西乘起来就完了。
时间复杂度 $O(n\log n)$。
代码：
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
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include<iostream>
#include<cstdio>
#include<map>
#define ll long long
using namespace std;
const ll N=1e5,mo=998244353,M=30;
ll n,cnt,ans;
ll p[M+5];
inline void Ins(ll x) {
for(ll i=51;i>=0;i--) {
if((x>>i)&1) {if(!p[i]) {p[i]=x;cnt++;break;}else x^=p[i];}
}
}
inline bool Ask(ll x) {
for(ll i=51;i>=0;i--) {if((x>>i)&1) x^=p[i];}return x==0;
}
inline ll qpow(ll b,ll p) {
ll res=1;while(p){if(p&1) res=res*b%mo;b=b*b%mo;p>>=1;}return res;
}
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
int main() {
n=read();
ans=1;
for(ll i=1;i<=n;i++) {ll x=read();ans=ans*qpow(2,cnt)%mo;Ins(x);}
write(ans);
return 0;
}
|
B.
咕。
C.
咕。