看了大神的博客

 除了排版累死人，别的讲的不错

抄了大神的模板，其实就是递归，只不过用for写的，类似于区间DP。复杂度nlogn

// 下标从0开始 n为2的幂次void FWT(int a[] ,int n){    for (int d = 1 ; d < n ; d <<= 1){        for (int m = d << 1 ,i = 0;i < n ; i+=m){            for (int j = 0 ; j < d ; j++){                int x = a[i+j],y = a[i+j+d];                //xor;                a[i+j] = (x+y) % mod,a[i+j+d] = (x-y+mod)%mod;                //and                //a[i+j]=x+y;                //or                //a[i+j+d]=x+y;            }        }    }}void UFWT(int a[],int n){    for (int d = 1 ; d < n ; d<<=1){        for (int m = d <<1, i = 0; i < n; i+=m){            for (int j = 0 ; j < d ; j++){                int x = a[i+j],y = a[i+j+d];                //xor                a[i+j] = 1LL*(x+y)*rev2%mod,a[i+j+d] = (1LL*(x-y)*rev2%mod + mod) % mod;                //and                //a[i+j] = x-y;                //or                //a[i+j+d] = y-x;            }        }    }}void solve(int a[],int b[],int n){    FWT(a,n);    FWT(b,n);    for (int i = 0 ; i

又看了一个例题

HDU 5909 这种树DP很常见，如果都是异或值可以这么优化，还有的需要类似FFT的优化。

很裸的DP

1 #include 
      
        2 const int mod = 1e9+7; 3 int rev2 = (mod+1)/2; 4 const double ex = 1e-10; 5 #define inf 0x3f3f3f3f 6 using namespace std; 7 // 下标从0开始 n为2的幂次 8 void FWT(int a[] ,int n){ 9     for (int d = 1 ; d < n ; d <<= 1){10         for (int m = d << 1 ,i = 0;i < n ; i+=m){11             for (int j = 0 ; j < d ; j++){12                 int x = a[i+j],y = a[i+j+d];13                 //xor;14                 a[i+j] = (x+y) % mod,a[i+j+d] = (x-y+mod)%mod;15                 //and16                 //a[i+j]=x+y;17                 //or18                 //a[i+j+d]=x+y;19             }20         }21     }22 }23 void UFWT(int a[],int n){24     for (int d = 1 ; d < n ; d<<=1){25         for (int m = d <<1, i = 0; i < n; i+=m){26             for (int j = 0 ; j < d ; j++){27                 int x = a[i+j],y = a[i+j+d];28                 //xor29                 a[i+j] = 1LL*(x+y)*rev2%mod,a[i+j+d] = (1LL*(x-y)*rev2%mod + mod) % mod;30                 //and31                 //a[i+j] = x-y;32                 //or33                 //a[i+j+d] = y-x;34             }35         }36     }37 }38 void solve(int a[],int b[],int n){39     FWT(a,n);40     FWT(b,n);41     for (int i = 0 ; i
       

E[1300];46 int dp[1300][1300];47 int ans[1300];48 int tmp[1300];49 int m;50 void dfs(int u,int fa){51 dp[u][a[u]] = 1;52 for (int i = 0 ; i