CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:fwt刷题 [2020/07/16 22:21]
infinity37
+++ 2020-2021:teams:wangzai_milk:fwt刷题 [2020/07/31 01:11] (当前版本)
infinity37 [HDU5909]
@@ 行 1: / 行 1: @@
 ====== 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解决这道题目了。
+<hidden><code c++>
+#include <bits/stdc++.h>
+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<len;i+=sz) {
+			for (int j = i;j < i+step;j++) {
+				long long a = src[j],b = src[j+step];
+				src[j] = (a+b)>>1;
+				src[j+step] = (a-b)>>1;
+			}
+		}
+	}
+}
+int main()
+{
+	int n,m;
+	scanf("%d%d",&n,&m);
+	for (int i = 0;i<n;i++)
+		scanf("%s",s[i]+1);
+	for (int i = 1;i<= m;i++) {
+		int tmp = 0;
+		for (int j = 0;j < n;j++)
+			tmp |= ((s[j][i]-'0')<<j);
+		cnt[tmp]++;
+	}
+	int len = 1<<n;
+	for (int i = 0;i<len;i++)
+	{
+		int tmp = calc(i);
+		dp[i] = min(tmp,n-tmp);
+	}
+	FWT(cnt,len);
+	FWT(dp,len);
+	for (int j = 0;j < len;j++)
+		dp[j] *= cnt[j];
+	IFWT(dp,len);
+	long long ans = n*m+1;
+	for (int j = 0;j < len;j++)
+		ans = min(ans,dp[j]);
+	printf("%lld\n",ans);
+	return 0;
+}
+</code></hidden>
+\\
 ==== CF914G ====
 ==== HDU5909 ====
+给定一个n个点的树，定义一个树的权值是书上所有点点权的异或值，问这个树权值为$[0,m)$的子图分别有多少个。
+直接树形dp，然后用fwt加速计算就行惹
+<hidden><code c++>
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <algorithm>
+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<hl;i++)
+    {
+        a[i] = (a[i]+a[i+hl])%mod;
+        a[i+hl] = ((a[i]-(a[i+hl]<<1))%mod+mod)%mod;
+        if(type==-1)
+        {
+            a[i] = (ll)a[i]*inv_2%mod;
+            a[i+hl] = (ll)a[i+hl]*inv_2%mod;
+        }
+    }
+    FWT(a,n>>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<d;i++)
+            res[i] = (ll)a[i]*b[i]%mod;
+        return res;
+    }
+}f[N],ans,zero;
+void init()
+{
+    for(d=1;d<m;d<<=1);
+    memset(f,0,sizeof(f));
+    memset(&ans,0,sizeof(ans));
+    memset(&zero,0,sizeof(zero));
+    zero[0] = 1;
+    zero.FWT(1);
+    memset(head,0,sizeof(head));
+    tot = 1;
+}
+void dp(int x,int fa)
+{
+    for(int i = head[x];i;i=e[i].next)
+        if(e[i].to!=fa)
+        {
+            dp(e[i].to,x);
+            f[x] = f[x]*(f[e[i].to]+zero);
+        }
+    ans = ans+f[x];
+}
+int main()
+{
+    int cas,x,y;
+    inv_2 = quikc_pow(2,mod-2);
+    scanf("%d",&cas);
+    while(cas--)
+    {
+        scanf("%d%d",&n,&m);
+        init();
+        for(int i = 1;i<= n;i++)
+        {
+            scanf("%d",&x);
+            f[i][x] = 1;
+            f[i].FWT(1);
+        }
+        for(int i = 1;i<n;i++)
+        {
+            scanf("%d%d",&x,&y);
+            add(x,y);
+        }
+        dp(1,0);
+        ans.FWT(-1);
+        for(int i = 0;i<m;i++)
+            printf("%d%c",ans[i],i==m-1?'\n':' ');
+    }
+    return 0;
+}
+</code></hidden>
+\\
 ==== HDU5823 ====
 ==== HDU6057 ====

CVBB ACM Team

用户工具

站点工具

页面工具