题目
一颗二叉树，每个点儿子个数为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| imes |g|) 的矩形上鞍点的个数
-
对于矩形上的每个点是相对独立的
-
所以(f)和(g)只要知道了有多少个不同的叶子节点也是独立的
-
设(f_i)表示改变(g)，有多少个(f)选到的叶子节点的集合大小为(i)，(g_i)同理，按照定义(dp)
-
设(p_i = sum_{j=1}^{K} j^{i-1})答案就是(K^{ 2L } imes (sum_{i=1}^{K}frac{f_ip_i}{K^i}) imes ( 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; }