n*m*m 做法

dp[i][j] 前i堆石子，异或和为j的方案数

 

 第一重循环可以矩阵快速幂优化

后面求出序列的生成函数可以FWT优化

 

做log次FWT也很慢（logn*m*logm）

两个合并就是倍增FWT，即先对生成函数的序列做一次正变换，对正变换得到的每个结果快速幂，最后逆变换回去

时间复杂度O（logn*m+m*logm）

 

生成函数：是质数则系数为1，否则为0

 

#include
     
      #include
      
       using namespace std;#define N 50001const int mod=1e9+7;const int M=1<<16;int inv;int a[N];int b[M+1];void FWT(int *a,int n){    int x,y;    for(int d=1;d
       
        <<=1)        for(int m=d<<1,i=0;i
        
         =mod ? mod : 0;                a[i+j+d]+=a[i+j+d]<0 ? mod : 0;            }}void IFWT(int *a,int n){    int x,y;    for(int d=1;d
         
          <<=1)        for(int m=d<<1,i=0;i
          
           >=1) if(b&1) res=1LL*res*a%mod; return res;}int main(){ for(int i=2;i