先对每一个求sg函数，暴力复杂度为$o(m^{2})$

取$k$满足$2^{k}\le x<2^{k+1}$（即$x$二进制下的最高位），考虑$y$与$2^{k}$的关系

1.若$1\le y<2^{k}$，那么必然有$1\le y\le x$，因此仅要求$0\le (x\oplus y)<x$

由于$y$的第$k$位为0且$x$的第$k$位为1，因此$2^{k}\le (x\oplus y)<x$，同时对于其中任意一个取值，根据异或的可逆性，都可以得到

2.若$2^{k}\le y\le x$，类似的必然有$0\le (x\oplus y)\le x-2^{k}$，同样其中任意一个取值都可以得到

换言之，$x$的后继的范围为$[0,x-2^{k}]\cup[2^{k},x)$，归纳$sg(x)=x-2^{k}+1$，则$sg(2^{k})=1$（其后继只有$sg(0)=0$），然后$sg(x)=mex(sg(0),sg([2^{k},x]))\ge x-2^{k}+1$

同时，由于$sg(x)\le x$，因此前面半段不能增加答案，即得到结论

进一步的，即求$\sum_{\bigoplus_{i=1}^{n}sg(a_{i})=0}1$，令$f_{n}(x)=\sum_{i=0}^{\infty}(\sum_{\bigoplus_{j=1}^{n}sg(a_{j})=i}1)x^{i}$，定义乘法为两式的异或卷积，即有$f_{n}(x)=f_{n-1}(x)f_{1}(x)=f^{n}_{1}(x)$，用快速幂+FWT计算，时间复杂度为$o(m\log_{2}n\log_{2}m)$

然后注意到FWT和IFWT的执行，在快速幂中存在重复，因此只需要在最开始和结尾执行一次，时间复杂度降为$o(m(\log_{2}mod+\log_{2}m))$，即可通过

1 #include
2 using namespace std;
3 #define mod 998244353
4 int n,ans,f[2000005];
5 long long m;
6 int main(){
7 scanf("%lld%d",&m,&n);
8 m%=mod-1;
9 for(int i=0;i<20;i++) 10 for(int j=(1<>=1;
25 }
26 }
27 for(int i=0;i<20;i++)
28 for(int j=0;j<(1<<20);j++)
29 if (j&(1<<i)){
30 int x=f[j],y=f[(j^(1<<i))];
31 f[(j^(1<<i))]=1LL*(mod+1)/2*(x+y)%mod;
32 f[j]=1LL*(mod+1)/2*(y+mod-x)%mod;
33 }
34 for(int i=1;i<(1<<20);i++)ans=(ans+f[i])%mod;
35 printf("%d",ans);
36 }