【清華集訓2017】福若格斯（不平等博弈）（Surreal Number）（生成函數）（二項式展開）

傳送門

講個笑話，把這道題A了才能算 “Surreal Number在不平等博弈中的應用” 入門

了解不能

題解：

不要以為雙方棋子屬性相同就不是不平等博弈了。。。

不平等博弈指的是在一個局面下輪到 L L L走， L L L能夠進行的合法操作和輪到 R R R走， R R R能夠進行的合法操作不同。

注意到這個是無環的而且有多個局面，而且還TM要計數，考慮用Surreal Number來描述這個遊戲。

由于題目說了隻有 23 23 23種情況，我們考慮大力把這些情況和目前這些局面的遊戲值手玩出來。

直接從初始狀态開始向下dfs即可手玩所有狀态。

然而當你玩到

LRL_R

的時候，如果你不平等博弈隻看過09年集訓隊論文，你就傻了。

這個狀态的 L L L決策為

LR_LR

， R R R決策為

LRLR_

，左右兩個都是 0 0 0,也就意味着目前狀态的Surreal Number表示為 { 0 ∣ 0 } \{0|0\} {0∣0}，09年集訓隊論文會告訴你這不是一個合法的Surreal Number。

不合法怎麼辦，棄了，還做個屁啊，這題肯定有鍋，考慮引入新記号。

設特殊記号 ∗ = { 0 ∣ 0 } , ↑ = { 0 ∣ ∗ } , ↓ = { ∗ ∣ 0 } *=\{0|0\},\uparrow=\{0|*\},\downarrow=\{*|0\} ∗={0∣0},↑={0∣∗},↓={∗∣0}為Surreal Number，并且它們不能用任何一個實數表示。

接下來的分析已經有點脫離了一般的Surreal Number理論了。

如果你隻想感性了解的話，我感覺沒門

容易發現 ∗ * ∗是一個先手必勝态，但是注意，不是所有先手必勝态都可以表示為* 。

同時根據Surreal Number中相反數的定義， ∗ = − ∗ *=-* ∗=−∗，也就是說 ∗ + ∗ = ∗ − ∗ = 0 *+*=*-*=0 ∗+∗=∗−∗=0，可以自己驗一下，在Surreal Number加法意義下這個也是成立的。同時根據實際意義可以發現 { ∗ ∣ ∗ } = 0 \{*|*\}=0 {∗∣∗}=0。

{ ∗ ∣ ∗ } = 0 , { 0 ∣ 0 } = ∗ \{*|*\}=0,\{0|0\}=* {∗∣∗}=0,{0∣0}=∗，這個看上去就很妙（雖然說這道題并不用）。

考慮一下 ↑ , ↓ \uparrow,\downarrow ↑,↓的實際含義。

考慮 ↑ = { 0 ∣ ∗ } \uparrow=\{0|*\} ↑={0∣∗}，如果此時該 L L L行動， L L L在執行過後會走到一個後手必勝的 0 0 0局面，此時的後手就是 L L L，如果 R R R執行了操作，就會走到一個先手必勝的 ∗ * ∗局面，此時先手還是 L L L。

我們發現單獨一個 ↑ \uparrow ↑局面是 L L L必勝，單獨一個 ↓ \downarrow ↓局面是 R R R必勝，現在問題在于我們要求和啊，隻知道單獨局面的結果是無法求和的，我們需要一個遊戲值，一個衡量赢面有多大的東西。

前面已經說了這個東西并不能用實數衡量，也就是說不能求和，而我們實際要考慮的其實就是求和結果和 0 0 0局面的大小關系。

求和考慮後繼局面，于是我們發現更加扯淡的是我們需要支援一個實數和 ∗ * ∗局面求和。。。

還有什麼辦法，硬推呗

待更新。。。。

代碼：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const

void file(){
#ifdef zxyoi
	freopen("frog.in","r",stdin);
#endif
	std::ios::sync_with_stdio(false);
}

using std::cin;
using std::cerr;
using std::cout;

cs int mod=998244353;
inline int add(int a,int b){return a+b>mod?a+b-mod:a+b;}
inline int dec(int a,int b){return a-b<0?a-b+mod:a-b;}
inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;}
inline int po(int a,int b){
	int r=1;for(;b;b>>=1,a=mul(a,a))
	if(b&1)r=mul(r,a);return r;
}
inline void Inc(int &a,int b){a+=b-mod;a+=a>>31&mod;}
inline void Dec(int &a,int b){a-=b;a+=a>>31&mod;}
inline void Mul(int &a,int b){a=mul(a,b);}

cs int N=1e6+7;
int fac[N],ifc[N];
void init_fac(){
	fac[0]=1;for(int re i=1;i<N;++i)fac[i]=mul(fac[i-1],i);
	ifc[N-1]=po(fac[N-1],mod-2);
	for(int re i=N-1;i;--i)ifc[i-1]=mul(ifc[i],i);
}
inline int C(int n,int m){
	return mul(fac[n],mul(ifc[m],ifc[n-m]));
}

void init_C(int n,int *a){
	for(int re i=0;i<=n;++i)a[i]=C(n,i);
}
int a[N],b[N],c[N];
// 0   1  2  3  4  5  6  7
//-1 -1/2 0 1/2 1  * up dn
int ct[11];
//<0, =0 ,>0
int num[15],ans[15],cnt[15];
int sign(int x){
	switch(x){
		case 1:return 3;
		case 0:return 2;
		case -1:return 1;
		default:return x<0?0:4;
	}
}
void solve(){
	int n,m=0;cin>>n;
	memset(ct,0,sizeof ct);
	memset(num,0,sizeof num);
	memset(ans,0,sizeof ans);
	memset(cnt,0,sizeof cnt);
	while(n--){
		std::string s;int x;
		cin>>s>>x;m+=x;
		if(s=="LL_RR")ct[5]+=x;
		if(s=="L_LRR")ct[6]+=x;
		if(s=="_LLRR")ct[2]+=x;
		if(s=="LRL_R")ct[5]+=x;
		if(s=="LR_LR")ct[2]+=x;
		if(s=="_RLLR")ct[0]+=x;
		if(s=="R_LLR")ct[2]+=x;
		if(s=="LRRL_")ct[4]+=x;
		if(s=="LRR_L")ct[2]+=x;
		if(s=="LRLR_")ct[2]+=x;
		if(s=="LR_RL")ct[1]+=x;
		if(s=="_RLRL")ct[0]+=x;
		if(s=="R_LRL")ct[2]+=x;
		if(s=="RRL_L")ct[4]+=x;
		if(s=="RR_LL")ct[2]+=x;
		if(s=="LLR_R")ct[7]+=x;
		if(s=="L_RLR")ct[5]+=x;
		if(s=="_LRLR")ct[2]+=x;
		if(s=="RL_LR")ct[3]+=x;
		if(s=="RLRL_")ct[4]+=x;
		if(s=="RLR_L")ct[2]+=x;
		if(s=="R_RLL")ct[0]+=x;
		if(s=="LLRR_")ct[2]+=x;
	}
	init_C(ct[0]+ct[4],a);//-1 ,1
	init_C(ct[1]+ct[3],b);//-1/2 ,1/2
	init_C(ct[7]+ct[6],c);//up ,dn
	for(int re i=1;i<=ct[1]+ct[3];++i)Inc(b[i],b[i-1]);
	for(int re i=0,j=ct[1]+ct[3],k=j;i<=ct[0]+ct[4];++i){
		while(~j&&(i-ct[0])*2+(j-ct[1])>=0)--j;
		while(~k&&(i-ct[0])*2+(k-ct[1])>0)--k;
		if(~j)Inc(num[0],mul(a[i],b[j]));
		if(~k)Inc(num[1],mul(a[i],b[k]));
	}
	num[2]=po(2,ct[0]+ct[1]+ct[2]+ct[3]+ct[4]);
	Mul(num[0],po(2,ct[2]));
	Mul(num[1],po(2,ct[2]));
	Dec(num[2],num[1]);
	Dec(num[1],num[0]);	
	for(int re i=0;i<=ct[6]+ct[7];++i)
	Inc(cnt[sign(i-ct[7])],c[i]);	
	ans[0]=mul(num[2],po(2,ct[5]+ct[6]+ct[7]));
	ans[1]=mul(num[0],po(2,ct[5]+ct[6]+ct[7]));
	if(ct[5]==0){
		Inc(ans[0],mul(num[1],cnt[3]+cnt[4]));
		Inc(ans[1],mul(num[1],cnt[0]+cnt[1]));
		Inc(ans[3],mul(num[1],cnt[2]));
	}else {
		int p=mul(po(2,ct[5]-1),num[1]);
		Inc(ans[0],mul(p,cnt[3]+cnt[4]));
		Inc(ans[1],mul(p,cnt[0]+cnt[1]));
		Inc(ans[3],mul(p,cnt[2]));
		Inc(ans[0],mul(p,cnt[4]));
		Inc(ans[1],mul(p,cnt[0]));
		Inc(ans[2],mul(p,add(cnt[1],add(cnt[2],cnt[3]))));
	}
	cout<<ans[0]<<" "<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<"\n";
}

signed main(){file();init_fac();int T,id;cin>>id>>T;while(T--)solve();return 0;}