Luogu4225 福若格斯

题面

简化题意

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

给出 $m$ 个局面，求所有局面的子集的胜负情况（先手/后手/L/R 必胜的局面数）。

$\sum m\leq 10^8$。

前言

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

但是，据一些题解说，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$。
• $\uparrow$ 表示 $\{0\mid\ast\}$，单独的一个 $\uparrow$ 局面可以推出是 L 必胜局面。因此可以认为，$\uparrow>0$，但是 $\uparrow$ 小于任何正数，无限趋近于 $0$。
• $\downarrow$ 表示 $\{\ast\mid 0\}$，单独的一个 $\downarrow$ 局面可以推出是 R 必胜局面。与 $\uparrow$ 类似。你可以将 $\downarrow$ 看作 $-\uparrow$。

则全部状态可以表示为：

（图片略丑 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$ 的数但是小于任何一个正数”一样）。
• $\{\ast\mid\ast\}=0$，因此任意两个 $\ast$ 会抵消。
• 可以得出，$\{\uparrow\mid\downarrow\}$ 是先手必胜策略。有 $\{\uparrow\mid\downarrow\}+\ast=0$，即 $\{\uparrow\mid\downarrow\}=-\ast=\ast$。
• $\uparrow+\downarrow=0$。前文提到过，可以将 $\downarrow$ 看作 $-\uparrow$。

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

• 若数字和 $\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;
}