====== FWT刷题 ====== ==== CF662C ==== 题意：给定一个n*m的01矩阵，可以取反若干次任意行或列，问若干次操作之后1最少是多少。数据范围：$n\leq 20,m\leq 100000$ 题解：n的范围很小，我们可以考虑二进制枚举行的取反策略，假设行的翻转策略为S，那么这道题目的答案就是$\sum_{i=1}^m min(f(S\oplus a_i),n-f(S\oplus a_i))$,f函数为这一列1的个数。那么我们假设$g(i)=min(f(i),n-f(i))$，那么原式就可以改写为$\sum_{j,i\oplus S = j}g(j)\times f(i)$,按照异或的性质，可以直接改写为 $\sum_{j,i\oplus j = S}g(j)\times f(i)$ 那么好了，接下来我们就可以轻松的用fwt解决这道题目了。


#include 
using namespace std;
const int V = 1<<20;
const int N = 22;
const int M = 100005;

int n,a[M];
long long dp[V],cnt[V];
char s[N][M];
int calc(int x) {
	int ans = 0;
	while (x) {
		ans+=(x&1);
		x>>=1;
	}
	return ans;
}

void FWT(long long *src,int len) {
	for (int sz = 2;sz <= len; sz<<=1) {
		int step = sz>>1;
		for (int i = 0;i < len;i+=sz) {
			for (int j = i;j < i+step;j++) {
				long long a = src[j],b = src[j+step];
				src[j] = a+b;
				src[j+step] = a-b;
			}
		}
	}
}

void IFWT(long long *src,int len) {
	for (int sz = 2;sz <= len;sz <<= 1) {
		int step = sz >> 1;
		for (int i = 0;i>1;
				src[j+step] = (a-b)>>1;
			}
		}
	}
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i = 0;i


\\
==== CF914G ====

==== HDU5909 ====
给定一个n个点的树，定义一个树的权值是书上所有点点权的异或值，问这个树权值为$[0,m)$的子图分别有多少个。

直接树形dp，然后用fwt加速计算就行惹


#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
int inv_2;
const int N = 1<<10;
const int mod = 1e9+7;
int quikc_pow(int x,int y)
{
    int res = 1;
    while(y)
    {
        if(y&1)res = (ll)res*x%mod;
        x = (ll)x*x%mod;
        y>>=1;
    }
    return res;
}
struct E
{int next,to;}e[N<<1];
int head[N],tot,d,n,m;
void add(int x,int y)
{
    e[++tot].to = y;e[tot].next = head[x];head[x] = tot;
    e[++tot].to = x;e[tot].next = head[y];head[y] = tot;
}
void FWT(int a[],int n,int type)
{
    if(n==1)return ;
    int hl = n>>1;
    for(int i = 0;i>1,type);
    FWT(a+hl,n>>1,type);
}
struct data
{
    int a[N];
    data(){memset(a,0,sizeof(a));}
    int& operator[](int x){return a[x];}
    void FWT(int type)
    {::FWT(a,d,type);}
    friend data operator +(data a,data b)
    {
        data res;
        for(int i = 0;i< d;i++)
            res[i]=(a[i]+b[i])%mod;
        return res;
    }
    friend data operator *(data a,data b)
    {
        data res;
        for(int i = 0;i
\\

==== HDU5823 ====

==== HDU6057 ====