[原创]HDU 5909 Tree Cutting [树形dp+FWT]【动态规划+数学】
2017-07-02 19:26:37 Tabris_ 阅读数:591
博客爬取于2020-06-14 22:39:50
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。https://blog.csdn.net/qq_33184171/article/details/74153824
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5909 ——————————————————————————————————————————
Tree Cutting Accepts: 14 Submissions: 119 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)
问题描述
Byteasar有一棵n n n 个点的无根树,节点依次编号为1 1 1 到n n n ,其中节点ii的权值为v i v_i v i 。
定义一棵树的价值为它所有点的权值的异或和。
现在对于每个[ 0 , m ) [0,m) [ 0 , m ) 的整数k k k ,请统计有多少T T T 的非空连通子树的价值等于k k k 。
一棵树TT的连通子树就是它的一个连通子图,并且这个图也是一棵树。
输入描述
第一行包含一个正整数T ( 1 ≤ T ≤ 10 ) T(1\leq T\leq10) T ( 1 ≤ T ≤ 10 ) ,表示测试数据的组数。
每组数据的第一行包含两个正整数n ( n ≤ 1000 ) n(n\leq 1000) n ( n ≤ 1000 ) 和m ( 1 ≤ m ≤ 2 10 ) m(1\leq m\leq 2^{10}) m ( 1 ≤ m ≤ 2 10 ) ,分别表示树的大小以及权值的上界。
第二行包含n n n 个整数v 1 , v 2 , v 3 , . . . , v n ( 0 ≤ v i < m ) v_1,v_2,v_3,...,v_n(0\leq v_i < m) v 1 , v 2 , v 3 , ... , v n ( 0 ≤ v i < m ) ,分别表示每个节点的权值。
接下来n − 1 n-1 n − 1 行每行包含两个正整数a i , b i ( 1 ≤ a i , b i ≤ n ) a_i,b_i(1\leq a_i,b_i\leq n) a i , b i ( 1 ≤ a i , b i ≤ n ) ,表示有一条连接a i a_i a i 和b i b_i b i 的无向边。
输入数据保证m m m 是2 2 2 的非负整数幂。
输出描述
对于每组数据,输出一行m m m 个整数,其中第i i i 个整数表示价值为i i i 的非空连通子树的数目。
因为答案很大,所以请模1 0 9 + 7 10^9+7 1 0 9 + 7 后输出。
输入样例 2 4 4 2 0 1 3 1 2 1 3 1 4 4 4 0 1 3 1 1 2 1 3 1 4
输出样例 3 3 2 3 2 4 2 3
——————————————————————————————————————————
很容易想到树形dp
设d p [ i ] [ j ] dp[i][j] d p [ i ] [ j ] 以第i i i 个节点为根的联通子树异或和为j j j 的数目.
转移的过程就是dp[u][i^j]+=dp[u][i]*dp[to][j];
这部分很好想到,但是复杂度却是O ( n m 2 ) O(nm^2) O ( n m 2 ) 的.
显然超时
然后有了一个FWT这种东西,快速沃尔什变换
和FFT类似,同样是将一个O ( n 2 ) O(n^2) O ( n 2 ) 的卷积运算转化为O ( n log n ) O(n\log n) O ( n log n ) 的.
FWT是
c[x] = \displaystyle\sum_{i \^ j=x} a[i]*b[j],与本题所求相同,套上去就好了
详细戳这里吧http://blog.csdn.net/liangzhaoyang1/article/details/52819835
附本题代码 ——————————————————————————————————————————
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 # include <bits/stdc++.h> typedef long long int LL; using namespace std; # define abs(x) ((x)>0?(x):-(x)) const int N = 1e3+7; const int MOD = 1e9+7; /*****************************************************************/ vector<int>G[N]; int w[N],dp[N][(1<<10)+9],ans[(1<<10)+9],tmp[(1<<10)+9]; int n,m,len; void FWT(int a[],int n){ for(int d=1;d<n;d<<=1) for(int m=d<<1,i=0;i<n;i+=m) for(int j=0;j<d;j++){ int x=a[i+j],y=a[i+j+d]; a[i+j]=(x+y)%MOD,a[i+j+d]=(x-y+MOD)%MOD; //xor:a[i+j]=x+y,a[i+j+d]=(x-y+MOD)%MOD; //and:a[i+j]=x+y; //or :a[i+j+d]=x+y; } } void UFWT(int a[],int n){ const int rev = (MOD+1)>>1; for(int d=1;d<n;d<<=1) for(int m=d<<1,i=0;i<n;i+=m) for(int j=0;j<d;j++){ int x=a[i+j],y=a[i+j+d]; a[i+j]=1LL*(x+y)*rev%MOD,a[i+j+d]=(1LL*(x-y)*rev%MOD+MOD)%MOD; //xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2; inv //and:a[i+j]=x-y; //or :a[i+j+d]=y-x; } } void solve(int a[],int b[],int n){ FWT(a,n); FWT(b,n); for(int i=0;i<n;i++) a[i]=1LL*a[i]*b[i]%MOD; UFWT(a,n); } void dfs(int u,int f=0){ for(int i=0;i<len;i++) dp[u][i]=0; dp[u][w[u]]=1; int gz=G[u].size(); for(int i=0,to;i<gz;i++){ to=G[u][i]; if(to==f) continue; dfs(to,u); for(int i=0;i<len;i++) tmp[i]=dp[u][i]; solve(tmp,dp[to],len); for(int i=0;i<len;i++) dp[u][i]=(dp[u][i]+tmp[i])%MOD; } for(int i=0;i<len;i++) ans[i]=(ans[i]+dp[u][i])%MOD; } int main(){ int _; for(scanf("%d",&_);_;_--){ scanf("%d %d",&n,&m); memset(ans,0,sizeof(ans)); for(len=1;len<m;len<<=1); for(int i=1;i<=n;i++)scanf("%d",&w[i]); for(int i=1,u,v;i<n;i++){ scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } dfs(1); for(int i=0;i<m-1;i++) printf("%d ",ans[i]); printf("%d\n",ans[m-1]); for(int i=1;i<=n;i++) G[i].clear(); } return 0; }