CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:fwt刷题 [2020/07/31 00:12]
infinity37
+++ 2020-2021:teams:wangzai_milk:fwt刷题 [2020/07/31 01:11] (当前版本)
infinity37 [HDU5909]
@@ 行 99: / 行 99: @@
 <hidden><code c++>
-#include <bits/stdc++.h>
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <algorithm>
 using namespace std;
-const int V = 1<<20;
+typedef long long ll;
-const int N = 22;
+int inv_2;
-const int M = 100005;
+const int N = 1<<10;
+const int mod = 1e9+7;
-int n,a[M];
+int quikc_pow(int x,int y)
-long long dp[V],cnt[V];
+{
-char s[N][M];
+    int res = 1;
-int calc(int x) {
+    while(y)
-	int ans = 0;
+    {
-	while (x) {
+        if(y&1)res = (ll)res*x%mod;
-		ans+=(x&1);
+        x = (ll)x*x%mod;
-		x>>=1;
+        y>>=1;
-	}
+    }
-	return ans;
+    return res;
 }
+struct E
-void FWT(long long *src,int len) {
+{int next,to;}e[N<<1];
-	for (int sz = 2;sz <= len; sz<<=1) {
+int head[N],tot,d,n,m;
-		int step = sz>>1;
+void add(int x,int y)
-		for (int i = 0;i < len;i+=sz) {
+{
-			for (int j = i;j < i+step;j++) {
+    e[++tot].to = y;e[tot].next = head[x];head[x] = tot;
-				long long a = src[j],b = src[j+step];
+    e[++tot].to = x;e[tot].next = head[y];head[y] = tot;
-				src[j] = a+b;
-				src[j+step] = a-b;
-			}
-		}
-	}
 }
+void FWT(int a[],int n,int type)
-void IFWT(long long *src,int len) {
+{
-	for (int sz = 2;sz <= len;sz <<= 1) {
+    if(n==1)return ;
-		int step = sz >> 1;
+    int hl = n>>1;
-		for (int i = 0;i<len;i+=sz) {
+    for(int i = 0;i<hl;i++)
-			for (int j = i;j < i+step;j++) {
+    {
-				long long a = src[j],b = src[j+step];
+        a[i] = (a[i]+a[i+hl])%mod;
-				src[j] = (a+b)>>1;
+        a[i+hl] = ((a[i]-(a[i+hl]<<1))%mod+mod)%mod;
-				src[j+step] = (a-b)>>1;
+        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 n,m;
+    int cas,x,y;
-	scanf("%d%d",&n,&m);
+    inv_2 = quikc_pow(2,mod-2);
-	for (int i = 0;i<n;i++)
+    scanf("%d",&cas);
-		scanf("%s",s[i]+1);
+    while(cas--)
-	for (int i = 1;i<= m;i++) {
+    {
-		int tmp = 0;
+        scanf("%d%d",&n,&m);
-		for (int j = 0;j < n;j++)
+        init();
-			tmp |= ((s[j][i]-'0')<<j);
+        for(int i = 1;i<= n;i++)
-		cnt[tmp]++;
+        {
-	}
+            scanf("%d",&x);
-	int len = 1<<n;
+            f[i][x] = 1;
-	for (int i = 0;i<len;i++)
+            f[i].FWT(1);
-	{
+        }
-		int tmp = calc(i);
+        for(int i = 1;i<n;i++)
-		dp[i] = min(tmp,n-tmp);
+        {
-	}
+            scanf("%d%d",&x,&y);
-	FWT(cnt,len);
+            add(x,y);
-	FWT(dp,len);
+        }
-	for (int j = 0;j < len;j++)
+        dp(1,0);
-		dp[j] *= cnt[j];
+        ans.FWT(-1);
-	IFWT(dp,len);
+        for(int i = 0;i<m;i++)
-	long long ans = n*m+1;
+            printf("%d%c",ans[i],i==m-1?'\n':' ');
-	for (int j = 0;j < len;j++)
+    }
-		ans = min(ans,dp[j]);
+    return 0;
-	printf("%lld\n",ans);
-	return 0;
 }
 </code></hidden>

CVBB ACM Team

用户工具

站点工具

页面工具