题意:树上每个节点有权值,定义一棵树的权值为所有节点权值异或的值。求一棵树中,连通子树值为[0,m)的个数。

分析:

设\(dp[i][j]\)为根为i,值为j的子树的个数。

则\(dp[i][j\oplus k] = dp[i][j\oplus k] +dp[i][j] * dp[v][k]\) ,但暴力枚举\(dp[i][j] * dp[v][k]\),每次的复杂度是\(O(M^2)\)的,总的复杂度将是\(O(NM^2)\),N和M都是1e3,不行。

实际上每次要求的,是个异或的卷积。可以用FWT来将复杂度优化至\(O(NMlogM)\)。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = (1<<10)+5;
typedef long long LL;
const int mod= 1e9+7;
LL dp[1005][MAXN];
LL ans[MAXN];
LL a[1005];
int N,M;
LL qpow(LL a,LL n)
{
LL res=1;
while(n){
if(n &1) res = res* a%mod;
a = a*a %mod;
n>>=1;
}
return res;
}
LL rev2 = qpow(2,mod-2); void FWT(LL 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++){
LL x = a[i+j],y = a[i+j+d];
a[i+j] = (x+y)%mod,a[i+j+d] = (x-y+mod)%mod; //取模
}
}
}
} void UFWT(LL 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++){
LL x = a[i+j],y = a[i+j+d];
a[i+j] = (x+y)*rev2%mod,a[i+j+d] = ((x-y)*rev2%mod + mod) % mod; //取模的情况
}
}
}
}
void solve(LL a[],LL b[],int n){
FWT(a,n);
FWT(b,n);
for (int i = 0 ; i<n ; i++)
a[i]=a[i]*b[i] %mod; //取模
UFWT(a,n);
} struct Edge{
int v,next;
}edges[2005];
int head[1005],tot;
void init(){
tot = 0;
memset(head,-1,sizeof(head));
} void AddEdge(int u,int v)
{
edges[tot] = (Edge){v,head[u]};
head[u] = tot++;
}
LL tmp[MAXN]; void dfs(int u,int fa)
{
dp[u][a[u]] = 1;
for(int i=head[u];~i;i=edges[i].next){
int v = edges[i].v;
if(v== fa) continue;
dfs(v,u);
for(int i=0;i<M;++i){
tmp[i] = dp[u][i];
}
solve(dp[u],dp[v],M);
for(int i=0;i<M;++i){
dp[u][i] = (dp[u][i] + tmp[i])%mod; //将之前
}
}
for(int i=0;i<M;++i){
ans[i] = (ans[i]+ dp[u][i]) %mod;
}
} int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int T; scanf("%d",&T);
while(T--){
init();
memset(dp,0,sizeof(dp));
memset(ans,0,sizeof(ans));
scanf("%d %d",&N, &M);
for(int i=1;i<=N;++i){
scanf("%lld",&a[i]);
}
for(int i=1,u,v;i<=N-1;++i){
scanf("%d %d",&u,&v);
AddEdge(u,v);
AddEdge(v,u);
}
dfs(1,-1);
for(int i=0;i<M;++i){
printf("%lld%c",ans[i],i==M-1?'\n':' ');
}
}
return 0;
}

最新文章

  1. Android中数据存储(一)
  2. Golang 效率初(粗)测
  3. 关于promise(一)
  4. 分布式Hadoop安装(二)
  5. C# 实例化多线程组
  6. Visual Studio原生开发的10个调试技巧(二)
  7. JS框架整理
  8. FZU 2104 (13.11.28)
  9. 装Oracle12C时遇到没有权限访问临时位置的解决方法
  10. LintCode 二叉树的层次遍历 II
  11. Ionic集成ArcGIS JavaScript API.md
  12. [luogu P3786]萃香抱西瓜 [spfa][状态压缩]
  13. C++ 之 Asio 库
  14. sql注入练习,sqli-labs writeup
  15. ORACLE导出导入意外终止导致 ORACLE initialization or shutdown in progress 问题解决
  16. mysql的coalesce使用技巧
  17. 修改input 的 placeholder
  18. noip模拟ernd
  19. vi/vim使用
  20. 前端规范--eslint standard

热门文章

  1. 学习《深入理解C#》—— 委托的构成、合并与删除和总结 (第二章1.1---1.4)
  2. Linq------错误: Unable to determine the principal end of an association between the types
  3. Linux命令之乐--expr
  4. 在静态工具类中需要注入mapper
  5. 【BZOJ2565】最长双回文串 Manacher
  6. MyBatis基础入门
  7. 浏览器中使用 ES6 import
  8. jQuery table tr隔行变色,鼠标移入移出变色,鼠标点击变色
  9. 1055 - Expression #1 of ORDER BY clause is not in GROUP BY clause and contains nonaggregated column &#39;information_schema.PROFILING.SEQ&#39; which is not functionally dependent on columns in GROUP BY clause
  10. spring data jpa 遇到的问题