簡單的博弈題
對于貪心的對手，顯然用最大的一半和他最小的一半比較判斷是否全勝。（這不就是田忌賽馬嗎）

對于隨機的對手，先考慮暴力怎么做：

void check(int x,int w){if(x>m){res+=(w>=m/2+1);return;}for(int i=1;i<=m;i++){if(visb[i]) continue;visb[i]=1;if(xa[x]>b[i]) check(x+1,w+1);else check(x+1,w);visb[i]=0;} } void dfs(int x){if(x>m){res=0;check(1,0);ans=max(ans,res);return;}for(int i=1;i<=m;i++){if(visa[i]) continue;visa[i]=1;xa[x]=a[i];dfs(x+1);visa[i]=0;} } int main(){inv[0]=inv[1]=1;for(int i=2;i<N;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;for(int i=1;i<N;i++) inv[i]=1ll*inv[i-1]*inv[i]%mod;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%lld",&a[i]);while(n--){scanf("%d",&op);for(int i=1;i<=m;i++) scanf("%lld",&b[i]);ans=0;dfs(1);ans=ans*inv[m]%mod;printf("%lld\n",ans);} }

由暴力中我們發現一件事：由于$a[],b[]$的配對情況固定，$第一個人使用任何策略都不影響他獲勝的概率$
也就是說我們只需選一種自己數字的排列并固定下來，再去和對手的數字的$m!$種全排列匹配即可。

暴力枚舉全排列顯然是不可接受的，考慮從小到大考慮自己的每個數，用$f_{i,j}$表示考慮了前$i$小的數，給其中$j$個匹配了比他小的數字的方案數。

思考$f_{i,j}$的轉移：
若給第$i$個數匹配比他小的數字：
$f_{i,j}\leftarrow f_{i?1,j?1}\times (p?(j?1))$
（其中$p$表示對手的數字中有$p$個小于$a[i]$）
若給第$i$個數匹配比他大的數字：
$f_{i,j}\leftarrow f_{i?1,j}\times q$
（其中$q$表示此時對手的數字中還剩$q$個比$a[i]$大的未匹配）

問題來了，要算出$q$，必須知道前$i?1$個數具體匹配了對手的哪些數，那不就跟暴力一樣了嗎？

對此，我們的解決方法是
若不給第$i$個數匹配比他小的數字，那么這個數先不匹配，即$f_{i,j}=f_{i?1,j}+f_{i?1,j?1}\times (p?(j?1))$
在考慮完自己的所有數后，我們再給還沒匹配的數統一匹配：
$f_{m,j}=f_{m,j}\times (m?j)!$
但這樣我們就不能保證所有數中$恰好$有$j$個數匹配到了比他小的數，事實上，$f_{m,j}表示所有數中$$至少$$有j個數匹配到了比他小的數的方案數$

根據廣義容斥原理/二項式反演，
設$g(k)$表示所有數中恰好有$k$個數匹配到了比他小的數 的方案數，
$f(k)$表示所有數中至少有$k$個數匹配到了比他小的數 的方案數，
$ans表示自己能贏的方案數$
$\because f(k)={\sum }_{i=k}^m{C}_i^{k}g(i)$ $（因此ans=f(?\frac{m+1}{2}?)）$
$\therefore g(k)={\sum }_{i=k}^m(?1{)}^{i?k}{C}_i^{k}f(i)$

記$w=?\frac{m+1}{2}?$，
$ans={\sum }_{k=w}^{m}g(k)={\sum }_{k=w}^m{\sum }_{i=k}^m(?1{)}^{i?k}{C}_i^{k}f(i)={\sum }_{i=w}^{m}f(i){\sum }_{k=w}^i(?1{)}^{i?k}{C}_i^k$
事實上，優化到這里已經能AC了

但這個式子還可以再優化：
引理1：${\sum }_{i=w}^n(?1{)}^{n?i}{C}_n^i=(?1{)}^{n?w}{C}_{n?1}^{w?1}$
證明1：

引理2：$C_n^i=C_{n?1}^{i?1}+C_{n?1}^i$
證明2：顯然

由引理2，$C_{n?1}^{i?1}=C_n^i?C_{n?1}^i$
$\because C_n^{i+1}=C_{n?1}^i+C_{n?1}^{i+1}$
$\therefore C_{n?1}^i=C_n^{i+1}?C_{n?1}^{i+1}$
$\therefore C_{n?1}^{i?1}=C_n^i?(C_n^{i+1}?C_{n?1}^{i+1})=C_n^i?C_n^{i+1}+C_{n?1}^{i+1}$
設$p_{i?1}=C_{n?1}^{i?1}$，那么
$p_{i?1}=C_n^i?C_n^{i+1}+C_{n?1}^{i+1}=C_n^i?C_n^{i+1}+p_{i+1}$
$\because p_{i+1}=C_n^{i+2}?C_n^{i+3}+p_{i+3}$
$\therefore p_{i?1}=C_n^i?C_n^{i+1}+C_n^{i+2}?C_n^{i+3}+p_{i+3}=C_n^i?C_n^{i+1}+C_n^{i+2}?C_n^{i+3}+C_n^{i+4}?C_n^{i+5}+...C_n^n$
$\therefore {\sum }_{i=w}^n(?1{)}^{n?i}{C}_n^i=(?1{)}^{n?w}{p}_{w?1}=(?1{)}^{n?w}{C}_{n?1}^{w?1}$
證畢

$\therefore ans={\sum }_{i=w}^{m}f(i){\sum }_{k=w}^i(?1{)}^{i?k}{C}_i^k={\sum }_{i=w}^m(?1{)}^{i?w}{C}_{i?1}^{w?1}f(i)$

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=10010; const int mod=998244353; int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } int f[N],a[N],b[N],fac[N],inv[N]; int power(int a,int b){int res=1;while(b){if(b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}return res; } void init(int n){fac[0]=1;for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;inv[n]=power(fac[n],mod-2);for(int i=n;i>=1;i--) inv[i-1]=1ll*inv[i]*i%mod; } int C(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod; } int n,m,op; int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) a[i]=read();sort(a+1,a+m+1);init(m);while(n--){scanf("%d",&op);for(int i=1;i<=m;i++) b[i]=read();sort(b+1,b+m+1);if(op==1){int ans=1;for(int i=1;i<=(m+1)/2;i++){if(b[i]>a[i+(m-1)/2]){ans=0;break;}}printf("%d\n",ans);} else{memset(f,0,sizeof(f));f[0]=1;for(int i=1;i<=m;i++){int p=lower_bound(b+1,b+m+1,a[i])-b-1;for(int j=p;j>=1;j--)f[j]=(f[j]+1ll*f[j-1]*(p-(j-1)))%mod;}for(int i=1;i<=m;i++)f[i]=1ll*f[i]*fac[m-i]%mod;int ans=0,tag=0;for(int i=(m+1)/2;i<=m;i++){int sum=1ll*C(i-1,(m-1)/2)*f[i]%mod;if(tag) sum=mod-sum;ans=(ans+sum)%mod;tag^=1;}ans=1ll*ans*inv[m]%mod;printf("%lld\n",ans);}}return 0; }

總結

以上是生活随笔為你收集整理的[XSY] 简单的博弈题（博弈+dp+组合数+容斥）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。