2020-2021:teams:wangzai_milk:fwt刷题
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:fwt刷题 [2020/07/17 00:02] infinity37 [CF662C] |
2020-2021:teams:wangzai_milk:fwt刷题 [2020/07/31 01:11] (当前版本) infinity37 [HDU5909] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== FWT刷题 ====== | ====== FWT刷题 ====== | ||
| - | 总之我先放一个题表在这里。 | ||
| ==== CF662C ==== | ==== CF662C ==== | ||
| 行 16: | 行 15: | ||
| 那么好了，接下来我们就可以轻松的用fwt解决这道题目了。 | 那么好了，接下来我们就可以轻松的用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 ==== | ==== CF914G ==== | ||
| ==== HDU5909 ==== | ==== 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 ==== | ==== HDU5823 ==== | ||
| ==== HDU6057 ==== | ==== HDU6057 ==== | ||
2020-2021/teams/wangzai_milk/fwt刷题.1594915378.txt.gz · 最后更改: 2020/07/17 00:02 由 infinity37
