2020-2021:teams:wangzai_milk:fwt刷题

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:fwt刷题 [2020/07/17 00:03]
infinity37 [CF662C]
+++ 2020-2021:teams:wangzai_milk:fwt刷题 [2020/07/31 01:11] (当前版本)
infinity37 [HDU5909]
@@ 行 1: / 行 1: @@
 ====== FWT刷题 ======
-总之我先放一个题表在这里。
 ==== CF662C ====
@@ 行 91: / 行 90: @@
 }
 </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 ====

2020-2021/teams/wangzai_milk/fwt刷题.1594915410.txt.gz · 最后更改: 2020/07/17 00:03 由 infinity37