11
2026-08-17 10:18:00
发布于：浙江
13阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
const int MOD=998244353,N=5005;
int f[N]; // f[j]：处理当前数字之前，Ushio比Fuuko多j个数字的方案数
int g[N]; // g[j]：处理完当前数字之后，Ushio比Fuuko多j个数字的方案数
int vis[N*2]; // vis[i]=1表示数字i必须放入Ushio的手牌
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--){
int n,m;
cin>>n>>m;
memset(vis,0,sizeof vis);
bool bad=0;
for(int i=1;i<=m;i++){
long long x;
cin>>x;
if(x>2*n) bad=1; // 必胜手牌中的数字不可能超过2n
else vis[x]=1; // 数字x必须属于Ushio
}
if(bad){
cout<<0<<endl;
continue;
}
memset(f,0,sizeof f);
f[0]=1; // 还没处理任何数字，双方数量差为0
for(int i=1;i<=2*n;i++){
memset(g,0,sizeof g); // 清空处理数字i之后的新方案数
int r=2*n-i; // 后面还剩下r个数字
for(int j=0;j<=n;j++){
if(!f[j]) continue;
// 数字i给Ushio，Ushio的数量优势增加1
if(j<n&&j+1<=r){
g[j+1]+=f[j];
if(g[j+1]>=MOD) g[j+1]-=MOD;
}
// 数字i给Fuuko，Ushio的数量优势减少1
if(!vis[i]&&j>0&&j-1<=r){
g[j-1]+=f[j];
if(g[j-1]>=MOD) g[j-1]-=MOD;
}
}
// 当前数字处理完了，让g成为下一轮的f
memcpy(f,g,sizeof f);
}
cout<<f[0]<<endl; // 最后双方各有n个数字，数量差为0
}
return 0;
}
/*
f[j]：处理数字i之前，Ushio比Fuuko多j个数字的方案数。
g[j]：处理完数字i之后，Ushio比Fuuko多j个数字的方案数。
数字i给Ushio：
g[j+1]=(g[j+1]+f[j])%MOD。
数字i给Fuuko：
g[j-1]=(g[j-1]+f[j])%MOD。
*/
有帮助，赞一个