【JZOJ6226】【20190618】纳什均衡

末蓝、 2021-12-11 06:49 348阅读 0赞

## 题目 ##

一颗二叉树，每个点儿子个数为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; }

转载于:https://www.cnblogs.com/Paul-Guderian/p/11050993.html