自动搬运

查看原文

来自洛谷，原作者为

	lllyyykkk 给岁月以文明，而非给文明以岁月

搬运于2025-08-24 23:08:06，当前版本为作者最后更新于2025-04-11 10:33:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

来一篇记忆化搜索的题解。
注：下文中加赛指的是有一个人分数超过 $11$ 分的情况。

题目传送门

首先先判断不合法的情况。

对于总局数，如果还没打到 $11$ 局或加赛之后总局数为奇数，则不合法。
对于比赛过程，比如得分与局数不符，分数倒退，已经获胜但比赛仍然进行，这些情况也不合法。

~这些信息有点离谱了。~

接下来，分讨两类。

$n \le 20$

直接记搜，为了方便，可以将最终的分数减一统计，不用判边界条件。

$n > 20$

参考样例提示的方法，我们先暴力记搜出两人十平的情况，接下来的对局因为必定是一分一分涨，套一个快速幂即可。

记搜时不要忘记判断不合法情况。

Code

#include <bits/stdc++.h>
using namespace std;
#define W return cout <<"0\n",void()
using ll=long long;
const int N=1e5+10,mod=998244353;
int n,T;
int a[N],b[N];
int f[20][20];
inline int ksm(int p,int q){
	int res=1;
	while(q){
		if(q&1) res=1ll*res*p%mod;
		q>>=1;p=1ll*p*p%mod;
	}
	return res;
}
inline bool J(int x,int y,int r){
	if((x==a[r]&&y==b[r])||(x==b[r]&&y==a[r])) return 0;
	return 1;
}
int dfs(int x,int y){
	if(!x&&!y) return 1;
	if(f[x][y]!=-1) return f[x][y];
	if(a[x+y]!=-1) if(J(x,y,x+y)) return f[x][y]=0;
	int res=0;
	if(x) res+=dfs(x-1,y);
	if(y) res+=dfs(x,y-1);
	return f[x][y]=res%mod;
}
inline void solve(){
	if(n<11||n>20&&(n&1)) W;
	for(int i=1,la=0,lb=0;i<n;i++){
		if(a[i]==-1) continue;
		if(max(a[i],b[i])<la||max(a[i],b[i])<lb||a[i]+b[i]!=i||(max(a[i],b[i])>=11&&abs(a[i]-b[i])>=2)) W;
		la=a[i],lb=b[i];
	}
	memset(f,-1,sizeof(f));
	if(n<=20){
		if(a[n]!=-1) if(J(11,n-11,n)) W;
		return cout <<(dfs(10,n-11)+dfs(n-11,10))%mod<<'\n',void();
	}
	else{
		if(a[n]!=-1) if(J((n>>1)+1,(n>>1)-1,n)) W;
		return cout <<1ll*dfs(10,10)*ksm(2,n-20>>1)%mod<<'\n',void();
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
		solve();
	}	
	return 0;
}