专栏文章

[清华集训 2017] 福若格斯 并不是题解而是超现实数入门（4）

MMatrixGroup时序绚乱
P4225题解参与者 12已保存评论 11

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
11 条
当前快照
1 份
快照标识符
@miqbig68
此快照首次捕获于
2025/12/04 02:05
3 个月前
此快照最后确认于
2025/12/04 02:05
3 个月前
查看原文
终于来到了这个系列的第 44 篇了呢……

题意

对于一个字符串，定义一次操作为，左方可以选取一个子串 L_\texttt{L\_} 替换成 _L\texttt{\_L} 或把 LR_\texttt{LR\_} 替换成 _RL\texttt{\_RL}，右方可以选取一个子串 _R\texttt{\_R} 替换成 R_\texttt{R\_} 或把 _LR\texttt{\_LR} 替换成 RL_\texttt{RL\_}。
有 mm 个字符串，每个字符串保证都可以由 LL_RR\texttt{LL\_RR} 进行若干操作得到，问在 2m2^m 种保留一个字符串的子集的情况，。字符串集按照所有本质不同字符串和它们出现的个数给出。数据随机生成。

超现实数基础

请参考本系列前篇：
与前几篇不同，本文引入一些和其它文献比较统一的记号：
{a,b,c,⋯∣d,e,f,⋯ }\{a,b,c,\cdots|d,e,f,\cdots\} 表示 ({a,b,c,⋯ },{d,e,f,⋯ })(\{a,b,c,\cdots\},\{d,e,f,\cdots\})
{fL+g}\{f_L+g\} 表示 {x+g∣x∈FL}\{x+g|x\in F_L\}，其中 f=(FL,FR)f=(F_L,F_R)。
例如，加法的定义为 f+g={fL+g,f+gL∣fR+g,f+gR}f+g=\{f_L+g,f+g_L|f_R+g,f+g_R\}。
以及，伪数/游戏也叫做博弈。

游戏的化简

之前我们的定理指出，对于游戏 gg，如果 a,b∈GLa,b\in G_L，且 a≤ba\le b，或者 a,b∈GRa,b\in G_R，且 a≥ba\ge b，则可以把 aa 删去。这一化简操作被称为删去被支配操作（dominated move）。实际上还有别的化简游戏的方式——跳过（bypass）可逆操作（reversible move）。
这里以右方的可逆操作为例，对于游戏 g={a,b,c,⋯∣d,e,f,⋯ }g=\{a,b,c,\cdots|d,e,f,\cdots\}，若存在 d∈GRd\in G_R，满足存在 d′∈DL≥gd'\in D_L\ge g，换言之左方可以行动使得 gg 反而对左方更不劣了，那这一步看起来就不太优。不过有可能右方是被迫的，因此需要跳过而不是删去。具体地，设 d′d' 的右集为 {x,y,z,⋯ }\{x,y,z,\cdots\}，则定义 h={a,b,c,⋯∣x,y,z,⋯ ,e,f,⋯ }h=\{a,b,c,\cdots|x,y,z,\cdots,e,f,\cdots\}。
定理 . g=hg=h。
证明 .
g≤hg\le h。只需验证 GL≱hG_L\ngeq h 且 g≱HRg\ngeq H_R。前者是显然的，因为每个 GLG_L 也同时是 HLH_L。后者也只需考虑不是 GRG_R 的 HRH_R，也就是那些 DR′D'_R，而显然有 g≤d′≱D′Rg\le d'\ngeq D'R。
g≥hg\ge h。只需要证 HL≱gH_L\ngeq g 且 h≱GRh\ngeq G_R。前者是显然的，因为每个 HLH_L 也同时是 GLG_L。后者也只需要考虑不是 HRH_R 的 GRG_R，也就是 dd。根据 ≥\ge 的定义，只要存在 w∈DLw\in D_L 满足 w≥hw\ge h，就可以证明 h≱dh\ngeq d。取 w=d′w=d'，则要证 d′≥hd'\ge h，只需换证 DR′≰hD'_R\nleq h 且 d′≰HLd'\nleq H_L。前者是显然的，因为每个 DR′D'_R 也同时是 HRH_R。而后者因为每个 HLH_L 都是 GLG_L，显然有 d′≥G≰GLd'\geq G\nleq G_L。
因此，如果存在某个 GLR≤gG_{LR}\le g 或 GRL≥gG_{RL}\ge g，就可以对可逆操作进行跳过！

上，下

定义. ↑={0∣∗},↓={∗∣0}\uparrow=\{0|\ast\},\downarrow=\{\ast|0\}。（分别读作「上」，「下」）
不难验证 ↓<0<↑\downarrow<0<\uparrow，且这两者互为相反数。一个自然的问题是，如果 ↑\uparrow 是正的，它有多正？
计算可得，L(↑)=R(↑)=R(0)L(\uparrow)=R(\uparrow)=R(0)，换言之，对于任意数 ε>0\varepsilon>0，都有 0<↑<ε0<\uparrow<\varepsilon。诶……？
定义 . 一个博弈 gg 是小的当且仅当对于任意数 ε>0\varepsilon>0，有 −ε<g<ε-\varepsilon<g<\varepsilon。
显然，小博弈可以为 00，可以是正的（↑\uparrow），可以是负的（↓\downarrow），也可以无关系（∗\ast）。显然，小博弈的和也是小的。
定义 . 一个博弈 gg 是全小的当且仅当它能走到的每个状态都是小的。
（当然这里可能需要忽略一些被支配的操作……暂时忽略一下严谨性吧。）
定义 . 对于一个博弈 gg，如果每走到一个等于数的位置就停下，那这些能走到的数被称为 gg 的停止位置。
定理 . 一个博弈 gg 是全小的，当且仅当它的每个停止位置都是 00。
证明 .
⇒\Rightarrow。如果它能走到一个停止位置不为 00 的地方，这个位置肯定不是全部小的。
⇐\Leftarrow。考虑我们计算 LL 和 RR 分割的过程。根据全部小博弈的定义，全部小博弈之间不可能有非 00 数。
引理 . 左集为空的博弈一定等于一个 ≤0\le0 的数，右集为空的博弈一定等于一个 ≥0\ge 0 的数。
证明 . 只需证后半句话，前半句话求个相反数即可。只需证明，存在某个数，满足它不小于等于左集里任何一个博弈即可。显然，对于任意博弈 g,g≤bday⁡gg,g\le \operatorname{bday}g，其中 bday⁡\operatorname{bday} 为其生日。（生日容易推广到所有博弈，它可以是任意的序数，一个序数嵌入超现实数的方式是，α={β∣}\alpha=\{\beta|\}，其中 β\beta 取遍所有小于 α\alpha 的序数）设 g={a,b,c,⋯∣}g=\{a,b,c,\cdots|\}，显然对于任意 gL∈GLg_L\in G_L 有 gL≱g≤bday⁡gg_L\ngeq g\le \operatorname{bday} g，这就证明了存在这么一个数。而最简单的这样的数 ≥0\ge 0 是简单的，因为负数都 ≤0\le 0，因此若负数符合 00 也符合，而 00 是最简单的数，即证。
定理 . 一个博弈是全小的，当且仅当它能走到的每个位置中，要么双方都能行动，要么双方都不能行动。
（当然，还是要认为 00 就不能走了……）
证明 . 根据引理，这等价于每个停止位置都是 00。
定理 . 全小博弈之和也是全小的。
证明 . 根据「要么双方都能行动，要么双方都不能行动」的判定进行归纳即可。
说回 ↑\uparrow 和 ↓\downarrow，我们知道它们和 ∗\ast 加起来肯定还是全部小的。能不能再具体一些？比如，∗+↑\ast+\uparrow 的左右集是什么呢？按照定义来的话，应该是 {↑,∗∣↑,0}\{\uparrow,\ast|\uparrow,0\}。首先，右集的 ↑\uparrow 是一个被支配的移动，可以删掉。其次，显然 ↑\uparrow 的右移动 ∗\ast 是 ≤∗+↑\le \ast+\uparrow 的，因此可以对 ↑\uparrow 进行跳过，得到最终化简结果是 {0,∗∣0}\{0,\ast|0\}。它的左右集都有 00，这显然和 00 无关系。

本题题解

本题就是给定若干个状态，问所有子集和中，>0>0，<0<0，=0=0 和 ∣∣0||0 的有多少个。我们首先要会如何判定一个子集和属于哪种情况。考虑画出博弈树。
值得一提的是初始局面 {↑∣↓}\{\uparrow|\downarrow\}。考虑能不能跳过一个可逆操作。看 ↑\uparrow 的右操作 ∗\ast 来判断它是否可逆，我们来看看是否有 ∗≤{↑∣↓}\ast\le \{\uparrow|\downarrow\}，这当且仅当 0≱{↑∣↓}0\ngeq \{\uparrow|\downarrow\} 且 ∗≱↓\ast\ngeq\downarrow。前者成立，因为 0≤↑≱{↑∣↓}0\le \uparrow\ngeq \{\uparrow|\downarrow\}，而后者也成立，因为我们论证过了 ∗+↑∣∣0\ast+\uparrow||0，则它相反数也是，两边加上 ∗\ast 就有 ∗∣∣↓\ast||\downarrow。因此 ↑\uparrow 是可逆的，可以跳过变成 00！↓\downarrow 也是对称的，因此它就等于 {0∣0}=∗\{0|0\}=\ast。不过嘛……我们论证过程里都有 ∗≤{↑∣↓}\ast\le \{\uparrow|\downarrow\}，反过来也一样，那不就是直接相等了嘛。
好的，也就是我们只需要判断若干数，↑\uparrow，↓\downarrow，∗\ast 的和与 00 的关系。记 n↑n\uparrow 为 nn 个 ↑\uparrow 的和，如果 nn 为负数，就是 −n-n 个 ↓\downarrow 的和。因为 ∗+∗=0\ast+\ast=0，我们只需要判断形如 c+n↑c+n\uparrow 和 c+∗+n↑c+\ast+n\uparrow 的博弈和 00 的关系即可。
首先，因为 ↑,↓,∗\uparrow,\downarrow,\ast 都是全部小的，若 cc 非零，则它和 00 的关系就是 cc 和 00 的关系。否则，对于 n↑n\uparrow，因为正的加正的还是正的，负的加负的还是负的，所以 n↑n\uparrow 和 00 的关系就是 nn 和 00 的关系。
接下来考虑 ∗+n↑\ast+n\uparrow。我们已经知道，∗+↓,∗,∗+↑\ast+\downarrow,\ast,\ast+\uparrow 都是和 00 无关系的。那下一个自然要考虑的就是 2↑+∗2\uparrow+\ast。
如何判断 ↑+↑≥∗\uparrow+\uparrow\ge \ast 是否成立？首先，↑+↑\uparrow+\uparrow 根据定义等于 {0+↑∣∗+↑}\{0+\uparrow|\ast+\uparrow\}。成立这当且仅当 ∗+↑≰∗\ast+\uparrow\nleq \ast 且 ↑+↑≰0\uparrow+\uparrow\nleq0。这两者均显然成立，故 ↑+↑≥∗\uparrow+\uparrow\ge \ast，而显然 ↑+↑≠∗\uparrow+\uparrow\neq \ast（因为一者 ≥0\ge 0 一者并不），因此 ↑+↑>∗\uparrow+\uparrow>\ast，即 ↑+↑+∗>0\uparrow+\uparrow+\ast>0。
反过来，↓+↓+∗<0\downarrow+\downarrow+\ast<0。因此 n↑+∗n\uparrow+\ast 在 n≥2n\ge2 时 >0>0，−1≤n≤1-1\le n\le 1 时 ∣∣0||0，n≤−2n\le -2 时 <0<0。
实际上我们可以得到下列等式：↑+↑+∗={0∣↑}\uparrow+\uparrow+\ast=\{0|\uparrow\}。这里不展开证明，∗\ast 移到右边按照定义展开一下就行。注意 ↑+↑≱{0∣↑}\uparrow +\uparrow\ngeq \{0|\uparrow\} 的理由是 ∗+↑≤{0∣↑}\ast+\uparrow\le \{0|\uparrow\}，而 ↑≱{0∣↑}\uparrow\ngeq \{0|\uparrow\} 的理由是 ∗≤{0∣↑}\ast \le \{0|\uparrow\}。
知道了怎么判定之后就容易多了。利用一下 Vandermonde 卷积化简组合数，写个前缀和就行。复杂度单次 O(m)O(m)。因为数据随机的，会有很多 00 位置（占 1023\dfrac{10}{23}）所以常数很小。

代码

CPP
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,del##i##verme=int(n);i<del##i##verme;++i)
#define rep1(i,n) for(int i=1,parano##i##a=int(n);i<=parano##i##a;++i)
#define per(i,n) for(int i=int(n)-1;i>=0;--i)
#define per1(i,n) for(int i=int(n);i>=1;--i)
typedef long long ll;
using namespace std;
const ll mod1=998244353;
int c0,cs,c1,cn1,ch,cnh,cu,cd;
// count of 0, *, 1, -1, 1/2, -1/2, up and down
int t;
int n,c;string s;
ll fac[1919810],ivf[1919810];
ll qkpw(ll a,ll b)
{
	ll r=1;
	while(b)
	{
		if(b&1) r=r*a%mod1;
		a=a*a%mod1;
		b>>=1;
	}
	return r;
}
void init()
{
	fac[0]=1;rep1(i,1048576) fac[i]=fac[i-1]*i%mod1;
	ivf[1<<20]=qkpw(fac[1<<20],mod1-2);per(i,1048576) ivf[i]=ivf[i+1]*(i+1)%mod1;
}
ll C(int x,int y)
{
	return fac[x]*ivf[y]%mod1*ivf[x-y]%mod1;
}
ll cpos,czero,cneg;
ll dpos,dneg,dfuz,dzero;
ll s0,s1;
ll anspos,ansneg,ansfuz,anszero;
int st[3141592];int V;
const int mod=int(mod1);
int query(int L,int R)
{
	L+=V;R+=V;
	L=min(2*V+1,max(1,L));R=max(1,min(2*V+1,R));
	int ans=st[R]-st[L-1];if(ans<0)ans+=mod;
	return ans;
}
void Q()
{
	cin>>n;
	c0=cs=c1=cn1=ch=cnh=cu=cd=0;
	rep(_,n)
	{
		cin>>s>>c;
		if(s=="L_LRR") cu+=c;
		else if(s=="LLR_R") cd+=c;
		else if(s=="RL_LR") ch+=c;
		else if(s=="LR_RL") cnh+=c;
		else if(s=="LRRL_"||s=="RLRL_"||s=="RRL_L") c1+=c;
		else if(s=="_RLLR"||s=="_RLRL"||s=="R_RLL") cn1+=c;
		else if(s=="LL_RR"||s=="L_RLR"||s=="LRL_R") cs+=c;
		else
		{
			// LLRR_ _LRLR R_LLR R_LRL LR_LR
			// _LLRR LRLR_ LRR_L RLR_L RR_LL
			c0+=c;
		}
	}
	cpos=czero=cneg=0;
	dpos=dzero=dneg=dfuz=0;
	anspos=ansneg=ansfuz=anszero=0;
	V=max(max(c1,cn1),max(ch,cnh))+3;
	memset(st,0,sizeof(int)*(2*V+3));
	for(int i=-ch;i<=cnh;++i) st[i+V]=int(C(ch+cnh,cnh-i));
	rep1(i,2*V+1)
	{
		st[i]+=st[i-1];if(st[i]>=mod)st[i]-=mod;
	}
	for(int i=-cn1;i<=c1;++i)
	{
		cpos=(cpos+query(-V,2*i-1)*C(c1+cn1,c1-i))%mod1;
		czero=(czero+query(2*i,2*i)*C(c1+cn1,c1-i))%mod1;
		cneg=(cneg+query(2*i+1,V)*C(c1+cn1,c1-i))%mod1;
	}
	ll mul=qkpw(2,c0);
	cpos=cpos*mul%mod1;
	czero=czero*mul%mod1;
	cneg=cneg*mul%mod1;
	if(cs==0)
	{
		s0=1;
		s1=0;
	}
	else
	{
		s0=s1=qkpw(2,cs-1);
	}
	for(int i=-cd;i<=cu;++i)
	{
		ll val=C(cu+cd,cu-i);
		if(i>=2) dpos=(dpos+val*(s0+s1))%mod1;
		else if(i<=-2) dneg=(dneg+val*(s0+s1))%mod1;
		else if(i==0)
		{
			dzero=(dzero+val*s0)%mod1;
			dfuz=(dfuz+val*s1)%mod1;
		}
		else if(i==1)
		{
			dpos=(dpos+val*s0)%mod1;
			dfuz=(dfuz+val*s1)%mod1;
		}
		else
		{
			dneg=(dneg+val*s0)%mod1;
			dfuz=(dfuz+val*s1)%mod1;
		}
	}
	anspos=(cpos*qkpw(2,cs+cu+cd)+czero*dpos)%mod1;
	ansneg=(cneg*qkpw(2,cs+cu+cd)+czero*dneg)%mod1;
	ansfuz=(czero*dfuz)%mod1;
	anszero=(czero*dzero)%mod1;
	cout<<anspos<<' '<<ansneg<<' '<<ansfuz<<' '<<anszero<<'\n';
}
int main()
{
	cin>>t;cin>>t;init();
	rep(i,t)Q();return 0;
}

参考文献

Donald E. Knuth, Surreal numbers, Addison-Wesley, 1974
John H. Conway, On Numbers And Games, 1976.
Elwyn R. Berlekamp, John H. Conway, Richard K. Guy, Winning Ways for Your Mathematical Plays, Second Edition, 2003.
马耀华, 浅谈超现实数与不平等博弈, IOI2021 中国国家候选队论文集, 2021.

评论

共 11 条评论，欢迎与作者交流。

正在加载评论...