HDU - 5909 Tree Cutting (树形dp+FWT优化)
2024-10-12 00:45:41
题意:树上每个节点有权值,定义一棵树的权值为所有节点权值异或的值。求一棵树中,连通子树值为[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;
}
最新文章
- Android中数据存储(一)
- Golang 效率初(粗)测
- 关于promise(一)
- 分布式Hadoop安装(二)
- C# 实例化多线程组
- Visual Studio原生开发的10个调试技巧(二)
- JS框架整理
- FZU 2104 (13.11.28)
- 装Oracle12C时遇到没有权限访问临时位置的解决方法
- LintCode 二叉树的层次遍历 II
- Ionic集成ArcGIS JavaScript API.md
- [luogu P3786]萃香抱西瓜 [spfa][状态压缩]
- C++ 之 Asio 库
- sql注入练习,sqli-labs writeup
- ORACLE导出导入意外终止导致 ORACLE initialization or shutdown in progress 问题解决
- mysql的coalesce使用技巧
- 修改input 的 placeholder
- noip模拟ernd
- vi/vim使用
- 前端规范--eslint standard
热门文章
- 学习《深入理解C#》—— 委托的构成、合并与删除和总结 (第二章1.1---1.4)
- Linq------错误: Unable to determine the principal end of an association between the types
- Linux命令之乐--expr
- 在静态工具类中需要注入mapper
- 【BZOJ2565】最长双回文串 Manacher
- MyBatis基础入门
- 浏览器中使用 ES6 import
- jQuery table tr隔行变色,鼠标移入移出变色,鼠标点击变色
- 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
- spring data jpa 遇到的问题