【2025广东省队集训day5】图上的游戏 做题记录

对于一个点有 $0$ 和 $1$ 两种颜色的有向图 $G$，定义其权值为 $0\to 1$ 边的条数减去 $1\to 0$ 的边的条数。

现在有一些点的颜色没有确定，Alice 和 Bob 开始博弈，Alice 先手。每次当前行动的人需要选择一个未确定颜色的点进行染色，Alice 想最大化最终 $G$ 的权值，而 Bob 想要最小化它。

两个人都绝顶聪明，故对于一个点的颜色 $\in \{0,1,2\}$（$2$ 表示颜色还没确定）的图 $G$，定义 $f(G)$ 为博弈完后 $G$ 的权值。

这个问题太简单了，所以现在给定了 $n$ 个点、它们的颜色 $a_i$和一个正整数 $m$，你要对每对 $1\le i\le n$ 且 $1\le j\le m$ 的 $(i,j)$ 求出点集为 $\{1,2,3,\dots,i\}$，点 $i$ 颜色为 $a_i$ 的所有 $j$ 条边的有向图 $G$ 的 $f(G)$ 的和，其中边被认为是两两不同的，即共有 $i^{2j}$ 个本质不同的 $G$。

$1\le n,m\le 50$。

首先第一步转化我就不会：$G$ 的权值相当于 $\sum\limits_{(u\to v)\in G}a_v-a_u$，即出点的颜色减去入点的颜色的和。

那么权值就能拆到点上了。具体的，权值相当于 $\sum\limits_u a_u\times (ind_u-oud_u)$。则博弈的过程就相当于每次可以启用或者禁用一个未被染色的点。

观察到 $\sum\limits_u ind_u-oud_u=0$，所以设 $c_u=ind_u-oud_u$，权值可以变为 $\frac{\sum\limits_{u}[a_u=1]\times c_u-\sum\limits_{u}[a_u=0]\times c_u}{2}$，也即博弈的过程变成每次选一个未被染色的点，将 $c_u$ 或者 $-c_u$ 加到权值上。

那么博弈的过程就确定了，两个人肯定都是按照 $|c_u|$ 从大到小选的，故 $f(G)$ 相当于给 $a_u=2$ 的 $u$ 按照 $|c_u|$ 排序后奇数位减偶数位的和。

现在考虑计数，不难发现两个 $0/1$ 之间的连边仅贡献方案数，因为反向后会抵消。进一步可以观察到 $2$ 和 $0/1$ 之间的连边也仅贡献方案数（考虑反向后 $|c_u|$ 没有改变）。

那么问题就简单了，考虑设 $f_{i,j,k,l}$ 表示考虑了 $i$ 个 $2$，当前 $|c_u|=j$，还剩下 $k$ 个互不相同的入度和 $l$ 个互不相同的出度，转移枚举 $|c_u|=x$ 的总共用了多少个即可，容易做到 $O(n^5\ln n)$（认为 $n,m$ 同阶），稍加分析可以分析道 $O(n^5)$，反正能过。

更好写的做法是直接枚举所有 $|c_u|=x$ 的出入度具体个数，做一个完全背包一样的东西。但我比较笨没写这个。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int S=55;

#define p 1000000007

int fra[S],inv[S],C[S][S];
int n,m,a[S];
int g[S][S][S][S]; // g[cnt2][c][cin][cou]: out-in=c
int f[S][S][S][S][2],h[S][S][S][S][2];
int ans[S][S][S]; // c01 c2 m

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

int main()
{
	for(int i=0;i<=S-3;i++)
	{
		if(i==0) fra[i]=1;
		else fra[i]=1ll*fra[i-1]*i%p;
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
	}
	inv[S-3]=qpow(fra[S-3],p-2);
	for(int i=S-3;i>=1;i--) inv[i-1]=1ll*inv[i]*i%p;
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=0;i<=m;i++) g[0][i][0][0]=1;
	for(int i=1;i<=n;i++)
		for(int c=0;c<=m;c++)
			for(int ci=0;ci<=m;ci++)
				for(int co=0;co<=m;co++)
				{
					int u=g[i-1][c][ci][co];
					if(u==0) continue;
					for(int x=0;x<=m-ci&&x+c<=m-co;x++)
						add(g[i][c][ci+x][co+x+c],
							1ll*u*C[ci+x][x]%p*C[co+x+c][x+c]%p);
				}
	f[0][m+1][m][m][0]=0;
	h[0][m+1][m][m][0]=1;
	for(int i=1;i<=n;i++) // 2
		for(int k=0;k<=m;k++) // in
			for(int l=0;l<=m;l++) // out
			{
				int u=0,cu=0;
				for(int j=m;j>=0;j--)
				{
					add(u,f[i-1][j+1][k][l][0]);
					add(u,f[i-1][j+1][k][l][1]);
					add(cu,h[i-1][j+1][k][l][0]);
					add(cu,h[i-1][j+1][k][l][1]);
					if(u!=0||cu!=0)
					{// in-out(0)
						for(int c=1;c*j<=k&&i+c-1<=n;c++)
							for(int co=0;co<=l&&co+c*j<=k;co++)
							{
								int ci=co+c*j;
								int pre=1ll*inv[c]
										*C[k][ci]%p*C[l][co]%p
										*g[c][j][co][ci]%p;
								add(f[i+c-1][j][k-ci][l-co][0],1ll*u*pre%p);
								if(c&1)
									add(f[i+c-1][j][k-ci][l-co][0],1ll*(i&1?j:p-j)*cu%p*pre%p);
								add(h[i+c-1][j][k-ci][l-co][0],1ll*cu*pre%p);
							}
					}
					if(j!=0) 
					{// out-in(1)
						int tu=(u+f[i-1][j][k][l][0])%p;
						int tcu=(cu+h[i-1][j][k][l][0])%p;
						if(tu==0&&tcu==0) continue;
						for(int c=1;c*j<=l&&i+c-1<=n;c++)
							for(int ci=0;ci<=k&&ci+c*j<=l;ci++)
							{
								int co=ci+c*j;
								int pre=1ll*inv[c]
										*C[k][ci]%p*C[l][co]%p
										*g[c][j][ci][co]%p;
								add(f[i+c-1][j][k-ci][l-co][1],1ll*tu*pre%p);
								if(c&1)
									add(f[i+c-1][j][k-ci][l-co][1],1ll*(i&1?j:p-j)*tcu%p*pre%p);
								add(h[i+c-1][j][k-ci][l-co][1],1ll*tcu*pre%p);
							}
					}
				}
			}
	// for(int c2=0;c2<=n;c2++)
		// for(int ci=0;ci<=m;ci++)
			// for(int co=0;co<=m;co++)
			// {
				// if(c2!=n||ci!=0||co!=0) continue;
				// int u=0;
				// for(int i=0;i<=m;i++)
					// add(u,f[c2][i][ci][co][0]),
					// add(u,f[c2][i][ci][co][1]);
				// for(int i=0;i<=m;i++)
					// printf("%d %d\n",1ll*f[c2][i][ci][co][0]*fra[c2]%p,
									 // 1ll*f[c2][i][ci][co][1]*fra[c2]%p);
				// printf(">> %d\n",1ll*u*fra[c2]%p);
			// }
	for(int c01=0;c01<=n;c01++)
		for(int c2=0;c2<=n-c01;c2++)
			for(int ci=0;ci<=m;ci++)
				for(int co=0;co<=m;co++)
				{
					int u=0;
					for(int i=0;i<=m;i++)
						add(u,f[c2][i][ci][co][0]),
						add(u,f[c2][i][ci][co][1]);
					for(int k=0;k<=ci&&k<=co;k++)
						add(ans[c01][c2][k],1ll*fra[c2]*u%p*
							qpow(c01,ci-k)%p*C[ci][k]%p*
							qpow(c01,co-k)%p*C[co][k]%p); 
				}
	for(int c01=0;c01<=n;c01++)
		for(int c2=0;c2<=n-c01;c2++)
			for(int ed=0;ed<=m;ed++)
				ans[c01][c2][ed]=1ll*ans[c01][c2][ed]*
					qpow(C[m][ed],p-2)%p*qpow(C[m][ed],p-2)%p*(p+1)/2%p;
	// cout<<ans[0][n][0]<<'\n';
	// return 0;
	int c[3]={0,0,0};
	for(int i=1;i<=n;i++)
	{
		c[a[i]]++;
		for(int j=1;j<=m;j++)
			cout<<ans[c[0]+c[1]][c[2]][m-j]<<' ';
		cout<<'\n';
	}
	return 0;
}