[2025 杭电春季赛 1]船长（模拟，数论）
[2025 杭电春季赛 1]船长（模拟，数论）
感觉这是一道有点难度的模拟题！杭电春季赛的题似乎都比较好，这道题很适合用来锻炼思维与码力。
题目
题目描述
大嘤帝国的东格玛男人，染染，终于成为了一名水手！
正如隔壁某位将军的那句“不想做将军的士兵不是好士兵”，不想做船长的水手不是好水手。作为一名好水手，染染自然也报名参与了船长的竞选。
报名那天，经过广泛的交流，染染得知，包括他自己在内，总共有 $n$ 名水手参与竞选。这 $n$ 名水手都被赋予了一个编号，可以认为第 $i$ 名参与竞选的水手的编号即为 $i$。特别的，染染的编号为 $p0$。
这 $n$ 名参与竞选的水手当然也不是谁都有竞争力的。根据染染的情报，只有 $k$ 名水手会对染染造成威胁，其中第 $j$ 名水手的编号为 $pj$，而染染当然不想在竞选时碰上这些对手。
竞选会持续若干轮，每轮会在仍在竞选的水手中大致筛选掉其中的一半，直至仍在竞选的水手只剩下一名，这一名水手就是最后的船长。在每一轮竞选中，假设仍在竞选的水手剩下 $m$ 名，编号从小到大依次为 $q1,q2,⋯,qm$，则水手 $q1$和水手 $q2$ 进行一次较量，水手 $q3$和水手 $q4$进行一次较量，依此类推总共进行 $⌊m/2⌋$（$m/2$，下取整）次较量，并剩下 $⌈m/2⌉$($m/2$ ， 上取正）名水手进入下一轮竞选。注意，如果 $m$ 为奇数，则水手 $qm$在本次竞选中不用参与任何一次较量，直接进入下一轮竞选。
现在，染染想要知道，如果他和其它水手的较量一定赢，而其他水手之间的较量双方赢的概率相等（即都是 $1/2$），则染染不会碰上会对染染造成威胁的 $k$ 名水手的概率对 $998244353$ 取模后的结果。
输入格式
本题单个测试点内包含多组测试数据。
输入第一行一个正整数 $T (1≤T≤20)$，表示数据组数。
每组数据第一行两个非负整数 $n (1≤n≤10^9)$和 $k (0≤k<min{n,10^5})$，分别表示参与竞选的水手数量和会对染染造成威胁的水手数量。
第二行$k+1$ 个两两不同的正整数 $p0,p1,p2,⋯,pk (1≤pj≤n)$，表示染染的编号和会对染染造成威胁的水手的编号。
保证单个测试点内每组数据中 $k+1$ 的和不超过 $10^6$。
输出格式
对于每组数据输出一行一个非负整数，表示答案概率对 $998244353$ 取模后的结果。
输入样例
3
10 0
1
8 2
1 3 5
4 2
1 3 4输出样例
1
623902721
0数据范围与提示
对于第一组样例，没有水手能对染染造成威胁，答案即为 $1$。
对于第二组样例，染染分别有可能在第二轮碰上水手 $3$ 和在第三轮碰上水手 $5$，碰上的概率分别为 $1/2$ 和 $1/4$，答案为 $(1−1/2)(1−1/4)=3/8$
对于第三组样例，不管第一轮竞选是水手 $3$ 还是水手 $4$ 赢，染染都会在第二轮碰上，所以答案为 $0$。
题解
前置知识
这道题需要算概率，我们无法用计算机方便地算分数，那么就需要用到`乘法逆元。
对于逆元，需要用一个快速幂来计算：
const int mod = 998244353;
int qp(int a,int b){
int res = 1;
a%=mod;
while(b){
if(b&1==1) res = res*a%mod;
a = a*a%mod;
b>>=1;
}
return res;
}
const int inv2 = qp(2, mod-2);
//int被宏定义为了long long
这里是两两竞选，分母只会是2，那就把2的逆元 $inv2$ 提前记录下来。
const int inv2 = qp(2, mod-2);思考
我们很容易可以发现，最后的概率由每一轮染染遇到有威胁对手的概率决定，而这些有威胁的对手可以出现在某轮的概率是可以计算出来的。另外，每一轮的水手的相对顺序也是不变的。通过这些信息，我们们就可以想到用开始给的信息计算出每一轮有威胁水手的概率和染染与他们较量的概率。
这看似是个很简单的模拟，但是需要一些小巧思。首先我们只对 $k$ 个有威胁的水手模拟，这是我们关注的，否则会超时。每一轮，用一个数组 $p$ 记录我们关注的水手的编号（包括染染,记录染染为 $p0$），用数组 $f$ 记录该轮每个水手出现的概率，并且分别用 $q$，$g$ 记录上述下一轮的信息进行迭代。每一轮都计算染染遇到有威胁水手的概率。
对每个水手的编号减一操作，这样的话这个编号除以2就是这个水手胜利后下一轮的编号，这样我们就可用来判断两个水手是否在本轮较量。这样做还有一个好处就是对编号和 $1$ 进行按位异或计算可以得到他的对手的编号。（话说这种方法谁能想到啊喂。）这样子就可以剩下许多代码上的麻烦。
对于每一轮我们可以做以下判断来进行迭代：
- 如果 $p0/2 == p[i]/2$，那么染染本轮有可能与编号为 $p[i]$ 的有威胁的水手较量，答案应该乘 $1-f[i]$ 。
- 如果 $p[i]/2==p[i+1]/2$，那么这两个有威胁的水手在本轮较量，下一轮 $p[i]/2$ 这个编号会产生有威胁的水手的概率为 $f[i]*f[i+1]*inv2$。
- 如果 $p[i]$ ^ $1>=n$，那么此水手本轮轮空。
- 如果上述条件都没有满足，那水手 $p[i]$本轮和没有威胁的水手较量，胜利概率$1/2$。
通过上述判断，就可以计算每轮的情况，再迭代给下一轮，直到只剩下染染一人，同时我们也得到了答案。
代码
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
const int mod = 998244353;
int qp(int a,int b){
int res = 1;
a%=mod;
while(b){
if(b&1==1) res = res*a%mod;
a = a*a%mod;
b>>=1;
}
return res;
}
const int inv2 = qp(2, mod-2);
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
for(int ti=1;ti<=t;++ti){
int n, k;
cin >> n >> k;
int p0;
cin >> p0;
p0--;
vector<int> p(k);
vector<int> f(k,1);
for(int i=0;i<k;++i){
cin >> p[i];
p[i]--;
}
sort(p.begin(), p.end());
int ans = 1;
while(p.size()){
vector<int> g,q;
for(int i=0;i<p.size();){
if(p0/2==p[i]/2){
ans *= (1+mod-f[i]+mod)%mod;
ans%=mod;
i++;
}
else if(i+1<p.size() && (p[i]/2 == p[i+1]/2)){
q.push_back(p[i]/2);
g.push_back((f[i]+f[i+1])%mod * inv2 % mod);
i+=2;
}
else if((p[i]^1)>=n){
q.push_back(p[i]/2);
g.push_back(f[i]%mod);
i++;
}
else {
q.push_back(p[i]/2);
g.push_back(f[i]*inv2%mod);
i++;
}
}
p = q;
f = g;
n = (n+1)/2;
p0/=2;
}
cout << (ans%mod+mod)%mod << "\n";
}
return 0;
}