Loading...

HDU5909 Tree Cutting

check评论:0 条 remove_red_eye浏览量:185 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-12-19

令$f[i][j]$代表$i$的子树中连通块异或和为$j$的个数

显然$f[i][j]$就是$i$各个子树中的联通块值异或和为$j$的联通块个数之积

(update:不是我没说清楚,我也不知道这个怎么描述比较好QwQ,感性理解吧)

显然$FWT$优化转移即可

 #include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7,inv2=5e8+4; 
int dp[1010][4050],val[1050],cnt,n,m,k,head[1010],tmp[1050];
int ans[1050];
struct edge
{
    int next,to;
}e[4010];
void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void FWT(int *x,int flag)
{
    for(int mid=1;mid<m;mid<<=1)
    {
        for(int k=0,r=(mid<<1);k<m;k+=r)
        {
            for(int i=0;i<mid;i++)
            {
                int dx=x[i+k],dy=x[i+mid+k];
                x[i+k]=(dx+dy)%mod,x[i+mid+k]=(dx-dy+mod)%mod;
                if(flag==0)
                {
                    x[i+k]=x[i+k]*inv2%mod;
                    x[i+mid+k]=x[i+mid+k]*inv2%mod;
                }
            }
        }
    }
}
void dfs(int u,int fa)
{
    dp[u][val[u]]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa)
        {
            continue;
        }
        dfs(v,u);
        for(int j=0;j<m;j++)
        {
            tmp[j]=dp[u][j];
        }
        FWT(dp[u],1),FWT(dp[v],1);
        for(int j=0;j<m;j++)
        {
            dp[u][j]*=dp[v][j];
            dp[u][j]%=mod;
        }
        FWT(dp[u],0);
        for(int j=0;j<m;j++)
        {
            dp[u][j]+=tmp[j]; 
            dp[u][j]%=mod;
        }
    }
    for(int i=0;i<m;i++)
    {
        ans[i]+=dp[u][i];
        ans[i]%=mod;
    }
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cnt=0;
        memset(dp,0,sizeof(dp));
        memset(head,0,sizeof(head));
        memset(ans,0,sizeof(ans));
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&val[i]);
        }
        for(int i=1;i<n;i++)
        {
            int x,y;
            scanf("%lld%lld",&x,&y);
            add(x,y),add(y,x);
        }
        dfs(1,0);
        for(int i=0;i<m;i++)
        {
            cout<<ans[i];
            if(i<m-1)
            {
                cout<<" ";
            }
        }
        puts("");
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名