HDU5959 Tree Cutting 树形DP+FWT优化异或卷积

本文主要是介绍HDU5959 Tree Cutting 树形DP+FWT优化异或卷积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考博客

https://www.cnblogs.com/Mychael/p/9255572.html

https://www.cnblogs.com/cjyyb/p/9065611.html

题意：给定一棵无根树，统计所有子树的异或和的个数。

dp[u][i],表示u为根的数，xor值得到i的方案数

显然，每次合并就是两个dp    dp值做xor   xor卷积

利用FWT优化异或卷积

然后被卡常

链式前向星更快

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define swap(a,b) (a^=b^=a^=b)
const ll maxn=2050;
const ll mod= 1e9+7;
ll inv2;
ll a[1<<17],b[1<<17],c[1<<17],N;
inline ll read()
{ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f;
}
inline void FWT_xor(ll *a,ll f)
{register ll i,j,p,k;for(i=1; i<N; i<<=1)for(p=i<<1,j=0; j<N; j+=p)for(k=0; k<i; ++k){ll X=a[j+k],Y=a[i+j+k];a[j+k]=(X+Y)%mod;a[i+j+k]=(X+mod-Y)%mod;if(f==-1)a[j+k]=1ll*a[j+k]*inv2%mod,a[i+j+k]=1ll*a[i+j+k]*inv2%mod;}
}
ll qpow(ll a,ll n)
{ll ans=1;while(n){if(n&1)ans=ans*a%mod;a=a*a%mod;n>>=1;}return ans;
}
ll dp[maxn][maxn];
vector<ll>v[maxn];
ll val[maxn];
void dfs(ll n,ll fa)
{dp[n][val[n]]=1;FWT_xor(dp[n],1);for(ll i=0; i<v[n].size(); i++){if(v[n][i]==fa)continue;ll to=v[n][i];dfs(to,n);//FWT_xor(dp[to],1);for(ll j=0; j<N; j++){dp[n][j]=dp[n][j]*(dp[to][j]+1)%mod;}//FWT_xor(dp[to],-1);}//FWT_xor(dp[n],-1);
}int main()
{inv2=qpow(2,mod-2);ll t,n,m,x,y;scanf("%lld",&t);while(t--){memset(dp,0,sizeof(dp));for(ll i=0; i<maxn; i++)v[i].clear();n=read();m=read();N=1;while(N<=m)N<<=1;for(ll i=1; i<=n; i++){val[i]=read();}for(ll i=0; i<n-1; i++){x=read();y=read();v[x].push_back(y);v[y].push_back(x);}dfs(1,0);for(ll i=1;i<=n;i++)FWT_xor(dp[i],-1);for(ll i=0; i<m; i++){ll ans=0;for(ll j=1; j<=n; j++){ans+=dp[j][i];ans%=mod;}printf("%lld",ans);if(i!=m-1)printf(" ");}printf("\n");}return 0;
}

 

 

这篇关于HDU5959 Tree Cutting 树形DP+FWT优化异或卷积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---