P4225 福若格斯

_Arahc_ · 2022-01-24 13:44:13 · 题解

upd：2021 集训队论文（2021 集训队论文集天翼云盘下载链接，访问码 ki6y）《浅谈超现实数与不平等博弈》一文的例题中有这个题（和更详细的题解），有需要可以下载。本文所述“不能只用到论文里的对超现实数的内容”，指的是 2009 年论文《浅谈如何解决不平等博弈问题》。

题意

具体题面还需要回原题看看。

两人玩一个有限状态非对称组合游戏。

给出 m 个局面，求所有 2^m 个子集（每个局面存在或不存在）的胜负结果（先手/后手/L/R 必胜的局面数）。

前言

从这个题开始学不平等博弈，但是显然这样对人非常不友好……建议还是先了解不平等博弈看几个裸题再回来……

但是，据一些题解说，A 了这个题才算“\text{surreal number} 在不平等博弈中的应用”到达入门级别……

建议先学习：

Matrix67 的 blog。
方展鹏 2009 集训队论文（天翼云盘下载链接，访问码：6xz7）。
《On Numbers and Games》（天翼云盘下载链接，访问码 ow4r），对本题而言可以直接从 CHAPTER 7 开始速成（反正我也只瞟了第七章）。中学英语水平就能看个大概，实在不行直接查单词，顺便积累词汇 qwq。

事实上，很不建议看那本书，会把你的精力耗空。除非你有充足的时间，可以考虑过一眼第七章的前几版，就可以回来切这个题了。

分析

输入数据 n 的范围直接告诉我们只有 23 种合法的状态。不难直接打出这样的爆搜：

map<string,int> mp;
inline void dfs(string a){
    if(mp.count(a)) return;
    mp[a]=mp.size();string b=a;
    for(register int i=0;i<5;++i) if(a[i]!='_'){
        if(a[i]=='L'){
            if(i<4 && a[i+1]=='_'){
                swap(b[i],b[i+1]);
                dfs(b);cout<<a<<" "<<b<<" L\n";
                swap(b[i],b[i+1]);
            }
            if(i<3 && a[i+2]=='_'){
                swap(b[i],b[i+2]);
                dfs(b);cout<<a<<" "<<b<<" L\n";
                swap(b[i],b[i+2]);
            }
        }
        else{
            if(i>0 && a[i-1]=='_'){
                swap(b[i],b[i-1]);
                dfs(b);cout<<a<<" "<<b<<" R\n";
                swap(b[i],b[i-1]);
            }
            if(i>1 && b[i-2]=='_'){
                swap(b[i],b[i-2]);
                dfs(b);cout<<a<<" "<<b<<" R\n";
                swap(b[i],b[i-2]);
            }
        }
    }
}

调用 dfs("LL_RR")，然后你就可以得到一张状态 DAG，长这个样子：

死局有五种，倒数第二行的 \text{LRR\_L,RR\_LL,R\_LLR}，还有第二行的 \text{\_LLRR,LLRR\_}。众所周知死局局面无论如何后手必胜，反推就能得到整个状态图所有节点的 \text{surreal number}。

但是如果只参考集训队论文的话，你就会发现 \{0\mid 0\} 在原文里被成为“不合法状态”。然而根据《On Numbers and Games》，这些状态又变成合法的。

这个题显然不会是一个不可做题，不然就不会变成一个 OJ 的题了，因此我们应当引入书上的概念，下面的符号均使用《On Numbers and Games》的符号：

0，1，-1 等实数表示不必多说。
* 表示 \{0\mid 0\}，是一种先手必胜状态。可以认为，\ast 小于任何正数，而大于任何负数，但是和 0 之间没有比较关系，而且有 \{\ast\mid\ast\}=0。

则全部状态可以表示为：

（图片略丑 qaq。）

得出本质不同的状态只有八种（0,1,-1,\frac{1}{2},-\frac{1}{2},\ast,\uparrow,\downarrow），而总状态数只有 23 种，因此直接打表。

根据 \text{surreal number} 定义：

若全部数字和 >0，L 必胜。
若全部数字和 <0，R 必胜。
若全部数字和 =0，后手必胜。

当然，在本题中，还要引入 \ast,\uparrow,\downarrow，考虑其性质（可以参考官方题解找到一些性质的证明）：

如果用实数表示的数字加起来不是 0，\ast,\uparrow,\downarrow 的影响都当作没有（正如前文“可以把 \uparrow 看成 >0 的数但是小于任何一个正数”一样）。
可以得出，\{\uparrow\mid\downarrow\} 是先手必胜策略。有 \{\uparrow\mid\downarrow\}+\ast=0，即 \{\uparrow\mid\downarrow\}=-\ast=\ast。

然后大力讨论一下，总结出下面结论：

若数字和 \neq 0，直接用正常的判定方法（即上文所说的判定法）。
若数字和 =0，\ast 有偶数个：
- 若 \sum\uparrow>0，L 必胜。
- 若 \sum\uparrow<0，R 必胜。
- 若 \sum\uparrow=0，后手胜。
若数字和 =0，\ast 有奇数个：
- 若 \sum\uparrow>1，L 必胜。
- 若 \sum\uparrow<-1，R 必胜。
- 否则，先手（注意还有多出来一个 \ast，可以推出应该是先手）必胜。

于是问题转化为如何计算这种规则下的数字和 >0,<0,=0 的方案数。当然你还需要考虑每个游戏有没有挂掉，所以本质是子集上的问题。

换句话说，要求出每个子集的：能用实数表示的数字的和 >0,=0,<0 的情况，和 \sum\uparrow>0,=0,<0（还有 >1,<-1,\in[-1,1]）的情况。

两个东西是同理的，所以考虑其中一个怎么做。

假设有 n 个 1，m 个 -1，那么有多少种方案可以使得 1 比 -1 选的数量恰好多 k 个？不难得到这样的式子：

\sum_{i=0}^{\min\{n,m-k\}}\binom{n}{i}\binom{m}{i+k}

结论：上式 =\binom{n+m}{n+k}。

证明：考虑组合意义，选择 i 个 1 和 i+k 个 -1，将其取相反数。最终得到的序列就是 n+m 个位置里面选择 n+k 个位置放 1。

证明搬运于这篇题解。

因此，枚举 1 比 -1 多几个，然后前缀和处理一下即可。

时间复杂度 \operatorname{O}(\sum m)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=2000006,mod=998244353;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
/*
0    -> 0
1    -> 1
-1   -> 2
0.5  -> 3
-0.5 -> 4
*    -> 5
up   -> 6
down -> 7
*/
inline int reads(){
    string buf;cin>>buf;
    if(buf=="LL_RR") return 5;
    if(buf=="_LLRR") return 0;
    if(buf=="LLRR_") return 0;
    if(buf=="L_LRR") return 6;
    if(buf=="LLR_R") return 7;
    if(buf=="LRL_R") return 5;
    if(buf=="L_RLR") return 5;
    if(buf=="LRLR_") return 0;
    if(buf=="LR_LR") return 0;
    if(buf=="_LRLR") return 0;
    if(buf=="LR_RL") return 4;
    if(buf=="_RLLR") return 2;
    if(buf=="LRRL_") return 1;
    if(buf=="RL_LR") return 3;
    if(buf=="_RLRL") return 2;
    if(buf=="LRR_L") return 0;
    if(buf=="R_LLR") return 0;
    if(buf=="RLRL_") return 1;
    if(buf=="R_LRL") return 0;
    if(buf=="RLR_L") return 0;
    if(buf=="RRL_L") return 1;
    if(buf=="R_RLL") return 2;
    if(buf=="RR_LL") return 0;
    return -1; // Invalid
}
inline int mi(int a,int p=mod-2){
    int res=1;
    while(p){
        if(p&1) res*=a,res%=mod;
        a*=a,a%=mod,p>>=1;
    }
    return res;
}

const int N=2000000;
int n,fac[max_n],inv[max_n];

inline int C(int n,int m){
    if(n<0 || m<0 || n<m) return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int s[max_n],s0,s1,sf1;

inline void Number(int c1,int cf1,int c2,int cf2){ // 1,-1,1/2,-1/2
    s0=s1=sf1=0;
    for(register int i=0;i<=c1+cf1;++i)
        s[i]=(C(c1+cf1,i)+(i?s[i-1]:0))%mod;
    for(register int i=0;i<=c2+cf2;++i){
        int k=(i-cf2)*2,p=C(c2+cf2,i);
        if(k>cf1)
            s1=(s1+p*s[c1+cf1])%mod;
        else if(k<-c1)
            sf1=(sf1+p*s[c1+cf1])%mod;
        else{
            s1 += p*(s[c1+cf1]-s[cf1-k])%mod,              s1=(s1+mod)%mod,
            sf1+= p*(cf1-k>0?s[cf1-k-1]:0)%mod,            sf1=(sf1+mod)%mod,
            s0 += p*(s[cf1-k]-(cf1-k>0?s[cf1-k-1]:0))%mod, s0=(s0+mod)%mod;
        }
    }
}

int p0,p1,p2,pf1,pf2;

inline void Special(int c1,int cf1){ // up, down
    p0=p1=p2=pf1=pf2=0;
    for(register int i=0;i<=c1+cf1;++i){
        int p=C(c1+cf1,i);
        if(i<cf1-1)  pf2=(pf2+p)%mod;
        if(i==cf1-1) pf1=(pf1+p)%mod;
        if(i==cf1)   p0=(p0+p)%mod;
        if(i==cf1+1) p1=(p1+p)%mod;
        if(i>cf1+1)  p2=(p2+p)%mod;
    }
}

int a[8],L,R,F,S;

signed main(){
    fac[0]=1;
    for(register int i=1;i<=N;++i)
        fac[i]=fac[i-1]*i%mod;
    inv[N]=mi(fac[N]);
    for(register int i=N-1;i>=0;--i)
        inv[i]=inv[i+1]*(i+1)%mod;
    n=read();
    for(register int T=read();T>0;--T){
        n=read(),L=R=F=S=0;
        for(register int i=0;i<8;++i) a[i]=0;
        for(register int i=1;i<=n;++i){
            int id=reads();
            a[id]+=read();
        }
        Number(a[3],a[4],a[1],a[2]),
        Special(a[6],a[7]);

        int t0=1,t1=0;
        if(a[5]) t0=t1=mi(2,a[5]-1);
        L+=s1*mi(2,a[5]+a[6]+a[7])%mod,L%=mod;
        R+=sf1*mi(2,a[5]+a[6]+a[7])%mod,R%=mod;

        // number=0
        L+=s0*t0%mod*(p1+p2)%mod+s0*t1%mod*p2%mod,    L%=mod;
        R+=s0*t0%mod*(pf1+pf2)%mod+s0*t1%mod*pf2%mod, R%=mod;
        F+=s0*t1%mod*(p0+p1+pf1)%mod,                 F%=mod;
        S+=s0*t0%mod*p0%mod,                          S%=mod;

        write(L*mi(2,a[0])%mod),putchar(' ');
        write(R*mi(2,a[0])%mod),putchar(' ');
        write(F*mi(2,a[0])%mod),putchar(' ');
        write(S*mi(2,a[0])%mod),putchar('\n');
    }
    return 0;
}