Noi online ා 2 improvement group question 3: Game

Noi online ා 2 improvement group question 3: Game

preface

This problem is the problem of trees.

I've been told all the questions

But I'm still dead.

subject

Portal

analysis

We note that the number of schemes with k k k times of non-equilibrium is g(k)g(k)g(k), and the number of schemes with kkk times of non-equilibrium is f(k)f(k)f(k). It is found that this is a binomial inversion form, and there are formulas for binomial inversion:

f(n)=∑i=nm(in)g(i)⇔g(n)=∑i=nm(−1)i−n(in)f(i)f(n)=\sum\limits_{i=n}^m{i\choose n}g(i)\Leftrightarrow g(n)=\sum\limits_{i=n}^m(-1)^{i-n}{i\choose n}f(i)f(n)=i=n∑m​(ni​)g(i)⇔g(n)=i=n∑m​(−1)i−n(ni​)f(i)

So we only ask f(k)f(k)f(k) f (k) to finish this problem. We can get fff from DP DP DP, and let dp[u][x]dp[u][x]dp[u][x] indicate that xxx pairs of points are chosen in the subtree of uuu, which are all in the relationship of ancestor and offspring (that is, xxx will win or lose). So I found that it can be calculated directly by tree backpack.

Transfer is a normal tree knapsack. At last, we need to consider the situation of a certain point and a certain descendant. In this case, the transfer is to select a point from the unsubscribed points in the subtree.

(Note: if there are K Matches, they must be selected. The rest can be selected or not. If there are exactly k matches, there must be exactly k matches.)

code

#include<bits/stdc++.h>
using namespace std;
const int Maxn=5006;
#define rep(i, a, b) for (int i=(a),i##end=(b);i<=i##end;++i) //Redefining for, I'll have a blog to explain later
#define per(i, a, b) for (int i=(a),i##end=(b);i>=i##end;--i)
const int Mod=998244353;
int n,Ar[Maxn];
int head[Maxn],nxt[Maxn<<1],to[Maxn<<1],cedge=0;
void adde(int u,int v)
{
	to[++cedge]=v;
	nxt[cedge]=head[u];
	head[u]=cedge;
}
int dp[Maxn][Maxn],Size[Maxn],sz[Maxn],pd[Maxn];
void dfs(int u,int fa)
{
	Size[u]=1;
	sz[u]=Ar[u];
	dp[u][0]=1;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dfs(v,u);
		rep(k,0,Size[u]+Size[v]) pd[k]=0;
		rep(j,0,min(Size[u],n/2))
		{
			if(dp[u][j])
			{
				rep(k,0,min(Size[v],n/2-j))
				{
					if(dp[v][k])
					{
						pd[j+k]=(pd[j+k]+dp[u][j]*1ll*dp[v][k]%Mod)%Mod;
					}
				}
			}
		}
		rep(k,0,Size[u]+Size[v]) dp[u][k]=pd[k];
        Size[u]+=Size[v];
		sz[u]+=sz[v];
	}
	per(i,min(sz[u],Size[u]-sz[u]),1)
	{
		dp[u][i]=(dp[u][i]+dp[u][i-1]*1ll*((Ar[u]?(Size[u]-sz[u]):(sz[u]))-(i-1))%Mod)%Mod;
	}
}
int J[Maxn],iJ[Maxn];
int Quick_Pow(int x,int a)
{
    int ret=1;
    while(a)
	{
        if(a&1) ret=1ll*ret*x%Mod;
        x=1ll*x*x%Mod;
		a>>= 1;
    }
    return ret;
}

int C(int x,int y)
{
    return J[x]*1ll*iJ[y]%Mod*iJ[x-y]%Mod;
}

int main()
{
	scanf("%d",&n);
    J[0]=iJ[0]=1;
    rep(i,1,Maxn-1) J[i]=J[i-1]*1ll*i%Mod,iJ[i]=Quick_Pow(J[i],Mod-2);
    rep(i,1,n)
        scanf("%1d",Ar+i);
    int u,v;
    rep(i,2,n) scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
    dfs(1,1);
    int re=0;
    rep(i,0,n/2+1) dp[1][i]=dp[1][i]*1ll*J[n/2-i]%Mod;
    rep(i,0,n/2)
	{
        re=0;
        rep(j,i,n/2)
            re+=C(j,i)*1ll*((j-i&1)?Mod-1:1)%Mod*dp[1][j]%Mod,re%=Mod;
        printf("%d\n",re);
    }
	return 0;
}

Tags: REST

Posted on Thu, 04 Jun 2020 08:03:06 -0700 by system_critical