【JZOJ6226】【20190618】纳什均衡

题目

一颗二叉树，每个点儿子个数为0 或 2 ，对每个叶子有一个权值$(c(u),d(u))$

从根结点开始走，Alice 可以选择奇数层的走法，Bob 可以选择偶数层的走法，分别获得最后走到叶子的c,d权值

设Alice的策略为f，Bob的策略为g，对于确定的(c,d)，一个(f,g)是nash均衡的当且仅当：

1.f不变，改变g都不能使得Bob获得的数更大； 2.g不变，改变f的值都不能使得Alice获得的数更大；

求叶子的权值范围为$(1-K,1-K)$的nash均衡点的个数和

$n \le 5000 \ , \ K \le 20 $

题解

做法一：
枚举最后选到的(C,D)，设$f_{u,0/1,0/1,0/1}$表示当前子树，改变奇数层能否让$C$更大，改变偶数层能否让$D$更大，能否走到$(C,D)$按照定义转移即可；
时间复杂度：$O(64nK^2)$
做法二：
对于一种(c,d)，nash点的个数就是$|f| \times |g|$ 的矩形上鞍点的个数
对于矩形上的每个点是相对独立的
所以$f$和$g$只要知道了有多少个不同的叶子节点也是独立的
设$f_i$表示改变$g$，有多少个$f$选到的叶子节点的集合大小为$i$，$g_i$同理，按照定义$dp$
设$p_i = \sum_{j=1}^{K} j^{i-1}$答案就是$K^{ 2L } \times (\sum_{i=1}^{K}\frac{f_ip_i}{K^i}) \times ( \sum_{ j=1 }^{ K } \frac{g_jp_j}{K^j})$
复杂度：$O(n ^ 2)$
有个奇怪的问题：
由于改变$f$和改变$g$得到的点的集合除了选到的点以外都是不相交的，

这意味着二维权值这个条件可能是彻底没有用的。。。。。。。。

//sol 1 :

 #include<bits/stdc++.h>

#define mod 998244353

#define pb push_back

using namespace std;

const int N=5010;

int n,K,fa[N],ch[N][2],dep[N],dp[N][2][2][2],C1,C2;

vector<int>sn[N];

void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;}

void dfs(int k){

	if(!sn[k].size()){

		dp[k][0][0][0]=C1*C2-1;

		dp[k][0][0][1]=1;

		dp[k][0][1][0]=C1*(K-C2);

		dp[k][1][0][0]=(K-C1)*C2;

		dp[k][1][1][0]=(K-C1)*(K-C2);

		return ;

	}

	int l=sn[k][0],r=sn[k][1];

	dfs(l);dfs(r);

	memset(dp[k],0,sizeof(dp[k]));

	for(int a1=0;a1<2;++a1)

	for(int b1=0;b1<2;++b1)

	for(int c1=0;c1<2;++c1)

	for(int a2=0;a2<2;++a2)

	for(int b2=0;b2<2;++b2)

	for(int c2=0;c2<2;++c2){

		int tmp=1l*dp[l][a1][b1][c1]*dp[r][a2][b2][c2]%mod;

		if(!(dep[k]&1)){

			inc(dp[k][a1|a2][b1][c1],tmp);

			inc(dp[k][a1|a2][b2][c2],tmp);

		}else{

			inc(dp[k][a1][b1|b2][c1],tmp);

			inc(dp[k][a2][b1|b2][c2],tmp);

		}

	}

}

int main(){

	freopen("nash.in","r",stdin);

	freopen("nash.out","w",stdout);

	scanf("%d%d",&n,&K);

	for(int i=2;i<=n;++i){

		scanf("%d",&fa[i]);fa[i]++;

		sn[fa[i]].pb(i);

		dep[i]=dep[fa[i]]+1;

	}

	int ans=0;

	for(C1=1;C1<=K;++C1)

	for(C2=1;C2<=K;++C2){

		dfs(1);

		inc(ans,dp[1][0][0][1]);

	}

	cout<<ans<<endl;

	return 0;

}

//sol 2 :

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#define PII pair<int,int>

#define MP make_pair

#define fir first

#define sec second

#define PB push_back

#define db long double

#define ll long long

using namespace std;

template <class T>

inline void rd(T &x) {

	x=0; char c=getchar(); int f=1;

	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }

	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;

}

const int N=5010,mod=998244353;

int Pow(int x,int y) {

	int res=1;

	while(y) {

		if(y&1) res=res*(ll)x%mod;

		x=x*(ll)x%mod,y>>=1;

	}

	return res;

}

int h[2][N][N],n,L;

int son[N][2],fa[N],sz[N];

int dep[N];

void dfs(int u) {

	if(!son[u][0]) return (void)(h[0][u][1]=h[1][u][1]=1,sz[u]=1);

	dfs(son[u][0]),dfs(son[u][1]);

	sz[u]+=sz[son[u][0]]+sz[son[u][1]];

	for(int c=0;c<2;++c) {

		if(c==dep[u]) {

			int cnt0=0,cnt1=0;

			for(int j=1;j<=L;++j) {

				cnt0=(cnt0+h[c][son[u][0]][j])%mod;

				cnt1=(cnt1+h[c][son[u][1]][j])%mod;

			}

			for(int j=1;j<=L;++j)

				h[c][u][j]=(h[c][son[u][0]][j]*(ll)cnt1+h[c][son[u][1]][j]*(ll)cnt0)%mod;

		}

		else {

			for(int j=1;j<=sz[son[u][0]];++j)

				for(int k=1;k<=sz[son[u][1]];++k)

					h[c][u][j+k]=(h[c][u][j+k]+h[c][son[u][0]][j]*(ll)h[c][son[u][1]][k])%mod;

		}

	}

}

int K,fp[N];

int main() {

	freopen("nash.in","r",stdin);

	freopen("nash.out","w",stdout);

	rd(n),rd(K);

	for(int i=2;i<=n;++i) {

		rd(fa[i]); ++fa[i];

		(son[fa[i]][0]?son[fa[i]][1]:son[fa[i]][0])=i;

		dep[i]=dep[fa[i]]^1;

	}

	for(int i=1;i<=n;++i) L+=!son[i][0];

	for(int i=1;i<=n;++i)

		for(int j=1;j<=K;++j)

			fp[i]=(fp[i]+Pow(j,i-1))%mod;

	dfs(1);

//	cerr<<"ok"<<endl;

	int t1=0,t2=0;

	for(int i=1;i<=L;++i) {

		t1=(t1+h[0][1][i]*(ll)fp[i]%mod*(ll)Pow(K,mod-1-i))%mod;

		t2=(t2+h[1][1][i]*(ll)fp[i]%mod*(ll)Pow(K,mod-1-i))%mod;

	}

	int ans=t1*(ll)t2%mod*Pow(K,2*L)%mod;

//	int ans=0;

//	for(int i=1;i<=L;++i)

//		for(int j=1;j<=L;++j)

//			ans=(ans+h[0][1][i]*(ll)h[1][1][j]%mod*fp[i]%mod*fp[j]%mod*Pow(K,2*L-i-j)%mod)%mod;

	printf("%d",ans);

	return 0;

}

巴特西

【JZOJ6226】【20190618】纳什均衡

题目

题解

最新文章

热门文章