T1 聪明的质检员
就是，我们考虑这样一个dp。
dpl,r表示当前我知道不合格品在[l,r]区间内，我有多大的概率算出来答案。
那么dp1,n就是我要的结果了。
那么，对于[l,r]来说，首先我有r−l+11的概率直接找到答案。
其次，有$lef=\frac{mid-l+1}{r-l+1},rig=1-lef-\frac{1}{r-l+1}$的概率不合格品在左边/右边。
而后续找到的前提条件是，我们得到了正确的提示：
也就是：P=∑i=2k+1kCkipi(1−p)k−i的概率得到正确的提示。
所以答案就是：
$dp_{l,r}=\frac{1}{r-l+1}+lef\times P\times dp_{l,mid}+rig\times P\times dp_{mid+1,r}$。
很显然地：我们只关心r−l的大小，所以直接用dplen来算即可。
由于当len是奇数的时候只会递归到两个一样的dp2len，len是偶数的时候会递归到一个dp2len和一个dp2len−1。容易发现有用的状态只有O(logn)种。
#include <bits/stdc++.h>
#define ll long long
#define maxn 200005
#define eps -1e-8
using namespace std;
map<ll,double> f;
double p,dui;
ll n,k;
ll C[15][15];
double dfs(ll n)
{
if (n<=2) return f[n]=1.0;
if (f.count(n)) return f[n];
ll lef,rig;
if (n&1) lef=rig=n/2; else lef=n/2-1,rig=n/2;
double zuo=1.0/n*lef,you=1.0/n*rig; //在左边的概率，在右边的概率
f[n]+=1.0/n;
f[n]+=dui*dfs(lef)*zuo+dui*dfs(rig)*you;
return f[n];
}
int main()
{
C[0][0]=1;
for (int i=1;i<=11;i++)
for (int j=0;j<=i;j++)
{
if (j==0 || i==1) C[i][j]=1; else C[i][j]=C[i-1][j]+C[i-1][j-1];
}
cin>>n>>p>>k;
for (int i=k/2+1;i<=k;i++)
{
double gai=1;
for (int j=1;j<=i;j++) gai*=p;
for (int j=1;j<=k-i;j++) gai*=(1-p);
gai*=C[k][i];
dui+=gai;
}
dfs(n);
printf("%.4lf\n",f[n]);
}
T2 乒乓球
source：某个CF题改编的简单版本。
30分的小数据模拟起来还是很简单的，不多说。
对于一条链，是在提示正解的：
我们考虑开个线段树维护一下区间内从0:0,1:0,0:1,1:1分别开始模拟一轮，一轮以后比分差是多少，小分是多少。
比如
0:0开始模拟一轮以后，比分差是1，小分是1:1。
1:0开始模拟一轮以后，比分差是−1，小分是0:1。
0:1开始模拟一轮以后，比分差是0，小分是1:1。
1:1开始模拟一轮以后，比分差是1，小分是1:0。
那么，从大的层面上来说，每一轮就会陷入：0:0->1:1->1:0->0:1->1:1->...的循环，在这个循环内的比分是1+−1+0=0，所以是平局。
那么正解就很简单了，我直接上树剖或者树上倍增，就可以维护好这个东西。
纯粹就是个小模拟，复杂度O(nlog2n)。
#include<bits/stdc++.h>
#define maxn 200005
#define ll long long
using namespace std;
//0 1 2 3
//0:0 1:0 0:1 1:1
struct nod{
int sta[4],score[4];
};
nod val[3];
nod init(int f)
{
nod ret;
if (f==1)
{
ret.sta[0]=1; ret.sta[1]=0; ret.sta[2]=3; ret.sta[3]=0;
ret.score[0]=0; ret.score[1]=1; ret.score[2]=0; ret.score[3]=1;
}
else if (f==0)
{
ret.sta[0]=2; ret.sta[1]=3; ret.sta[2]=0; ret.sta[3]=0;
ret.score[0]=0; ret.score[1]=0; ret.score[2]=-1; ret.score[3]=-1;
}
else
{
for (int i=0;i<=3;i++) ret.sta[i]=i,ret.score[i]=0;
}
return ret;
}
nod merge(nod x,nod y)
{
nod ret;
for (int fir=0;fir<=3;fir++)
{
int score=0;
int now=fir;
score+=x.score[now]; now=x.sta[now];
score+=y.score[now]; now=y.sta[now];
ret.score[fir]=score; ret.sta[fir]=now;
}
return ret;
}
int n,Q;
int u,v,w;
basic_string<int> edge[maxn];
int fa[maxn][21],dep[maxn];
//F表示从你向上，G表示从父亲到你
nod F[maxn][21],G[maxn][21];
void dfs(int x,int father,int v)
{
dep[x]=dep[father]+1;
fa[x][0]=father; for (int i=1;i<=19;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
F[x][0]=val[v]; G[x][0]=val[v];
for (int i=1;i<=19;i++)
{
F[x][i]=merge(F[x][i-1],F[fa[x][i-1]][i-1]);
G[x][i]=merge(G[fa[x][i-1]][i-1],G[x][i-1]);
}
for (int y:edge[x])
{
int id=abs(y),tag=(y<0?1:0);
if (id!=father) dfs(id,x,tag);
}
}
void out(nod x)
{
for (int i=0;i<=3;i++) cout<<x.sta[i]<<" "<<x.score[i]<<endl;
}
int mem[4];
void check(nod x)
{
mem[0]=0; mem[1]=mem[2]=mem[3]=1<<29;
int now=0,score=0;
while (true)
{
score+=x.score[now]; now=x.sta[now];
if (mem[now]!=(1<<29))
{
int cha=score-mem[now];
if (cha>0) cout<<"Win\n";
if (cha==0) cout<<"Draw\n";
if (cha<0) cout<<"Lose\n";
return;
}
mem[now]=score;
}
return;
}
void work(int u,int v)
{
nod a=val[2],b=val[2];
int cha=dep[u]-dep[v];
if (cha>0)
{
for (int i=19;i>=0;i--)
if ((cha>>i)&1)
{
a=merge(a,F[u][i]);
u=fa[u][i];
}
}
else if (cha<0)
{
cha=-cha;
for (int i=19;i>=0;i--)
if ((cha>>i)&1)
{
b=merge(G[v][i],b);
v=fa[v][i];
}
}
if (u==v) {check(merge(a,b)); return;}
for (int i=19;i>=0;i--)
if (fa[u][i]!=fa[v][i])
{
a=merge(a,F[u][i]); u=fa[u][i];
b=merge(G[v][i],b); v=fa[v][i];
}
a=merge(a,F[u][0]); u=fa[u][0];
b=merge(G[v][0],b); v=fa[v][0];
check(merge(a,b));
return;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
val[0]=init(0); val[1]=init(1); val[2]=init(2);
cin>>n;
for (int i=1;i<n;i++)
{
cin>>u>>v>>w;
if (w==0) edge[u]+=v,edge[v]+=u;
else edge[u]+=-v,edge[v]+=-u;
}
dfs(1,1,2);
cin>>Q;
while (Q--)
{
cin>>u>>v;
work(u,v);
}
}
T3 田忌赛马
bonus：有一个神秘的不依赖随机数据的莫队做法，见WYR的题解。
source：瞎编的。
首先，我们可以把星粉剂想象成，每次可以给一个数字+1。
45分：
我们考虑一下询问的区间a,b里面分别有多少个1,2,3,...,n。
假设≤5的ai有x个，≤4的bi有y个，那么显然：有x−y个≤5的数字要变得≥5，假设=5的bi有z个，那么：我们需要从x−y个数字中，挑选x−y−z个变得≥6。
我们设Ai表示a数组中有多少个≤i的数字，Bi表示b数组中有多少个≤i的数字，那么：
∏i=1mxCAi−Bi−1Ai−Bi
就是答案了。
那么对于mx≤1000的小数据，我们直接暴力求出A,B数组即可。注意一个细节是如果你数组开了2×2e5×1000，会喜提MLE。
100分：
这个好容易想到的其实。
这是随机数据诶，随机数据性质多多。
我们对于每次li,ri，从ali,bri分别向右/向左暴力，一旦遇到一个位置算出来的系数跟Ai,Bi一样，就说明中间这一段都一样，直接用之前的答案就好了。
至于维护区间里有多少个范围内的数字，直接用主席树即可（实际上这个过程可以只在一开始主席树查一遍，之后的询问直接在这个基础上指针跑一跑就可以线性了）。
时间复杂度在随机数据下是：O(nlogn+kQlogn)。
可以通过上述优化把复杂度变成：O(nlogn+kQ+Qlogn)，这样就能卡掉莫队了。
#include<bits/stdc++.h>
#define maxn 200005
#define ls lson[now]
#define rs rson[now]
#define mid ((l+r)>>1)
#define ll long long
#define mod 998244353
using namespace std;
ll pw(ll x,ll mi)
{
ll ret=1;
while (mi)
{
if (mi&1) ret=ret*x%mod;
mi=mi>>1; x=x*x%mod;
}
return ret;
}
ll fac[maxn],inv[maxn],ni[maxn];
ll cc(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
void init2(int zd)
{
ni[0]=ni[1]=1;
for (int i=2;i<=zd;i++) ni[i]=(mod-(mod/i)*ni[mod%i]%mod);
fac[0]=fac[1]=inv[0]=1;
for (int i=2;i<=zd;i++) fac[i]=fac[i-1]*i%mod;
inv[zd]=pw(fac[zd],mod-2);
for (int i=zd-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
return;
}
int rt1[maxn],rt2[maxn],tot=0;
int sum[maxn<<6],lson[maxn<<6],rson[maxn<<6];
ll a[maxn],b[maxn];
ll ans[maxn];
ll x[maxn],y[maxn];
int n;
int tx[maxn],ty[maxn];
void ins(int &now,int pre,int l,int r,int id)
{
if (!now) now=++tot;
if (l==r) {sum[now]=sum[pre]+1; return;}
if (id<=mid) {ins(lson[now],lson[pre],l,mid,id); rson[now]=rson[pre];}
else {ins(rson[now],rson[pre],mid+1,r,id); lson[now]=lson[pre];}
sum[now]=sum[lson[now]]+sum[rson[now]];
}
int query(int now,int l,int r,int L,int R)
{
if (!now || L>R) return 0;
if (L<=l && r<=R) return sum[now];
int ret=0;
if (L<=mid) ret+=query(lson[now],l,mid,L,R);
if (mid+1<=R) ret+=query(rson[now],mid+1,r,L,R);
return ret;
}
void out(int l,int r,int *a)
{
for (int i=l;i<=r;i++) cout<<a[i]<<" "; cout<<endl;
}
void work(int l,int r)
{
ll ret=1,L=-1,R=-1;
for (int i=a[l];i<=b[r];i++)
{
int shang=query(rt1[r],1,n,1,i)-query(rt1[l-1],1,n,1,i);
int xia=query(rt2[r],1,n,1,i-1)-query(rt2[l-1],1,n,1,i-1);
int xia2=query(rt2[r],1,n,1,i)-query(rt2[l-1],1,n,1,i);
tx[i]=shang-xia; //一共还剩这么多数字
ty[i]=shang-xia2; //要搬这么多数字走
ret=ret*cc(tx[i],ty[i])%mod;
if (tx[i]==x[i] && ty[i]==y[i]) {L=i; break;}
}
if (L==-1) {cout<<ret<<"\n"; return;} //两端碰撞了
for (int i=b[r];i>L;i--)
{
int shang=query(rt1[r],1,n,1,i)-query(rt1[l-1],1,n,1,i);
int xia=query(rt2[r],1,n,1,i-1)-query(rt2[l-1],1,n,1,i-1);
int xia2=query(rt2[r],1,n,1,i)-query(rt2[l-1],1,n,1,i);
tx[i]=shang-xia; //一共还剩这么多数字
ty[i]=shang-xia2; //要搬这么多数字走
ret=ret*cc(tx[i],ty[i])%mod;
if (tx[i]==x[i] && ty[i]==y[i]) {R=i; break;}
}
if (R==-1 || R==L+1) {cout<<ret<<"\n"; return;} //两端碰撞了
//还要乘上L+1~R-1
ret=ret*pw(ans[L],mod-2)%mod*ans[R-1]%mod;
cout<<ret<<"\n";
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
init2(200000);
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++) cin>>b[i];
for (int i=1;i<=n;i++)
{
ins(rt1[i],rt1[i-1],1,n,a[i]);
ins(rt2[i],rt2[i-1],1,n,b[i]);
}
//搞定初始的答案
for (int i=1;i<=n;i++)
{
int shang=query(rt1[n],1,n,1,i);
int xia=query(rt2[n],1,n,1,i-1),xia2=query(rt2[n],1,n,1,i);
x[i]=shang-xia; //一共还剩这么多数字
y[i]=shang-xia2; //要搬这么多数字走
}
ans[0]=1;
for (int i=1;i<=n;i++) ans[i]=ans[i-1]*cc(x[i],y[i])%mod;
int Q; cin>>Q;
// for (int i=1;i<=b[n];i++) cout<<x[i]<<" "; cout<<endl;
// for (int i=1;i<=b[n];i++) cout<<y[i]<<" "; cout<<endl;
int l,r;
while (Q--)
{
cin>>l>>r;
work(l,r);
}
}
这是一个不依赖数据随机的 O(n+q) 做法。
考虑先求出两个数组匹配的方案数，满足任意一组匹配 (x,y) 都有 ax≤by。
容易发现求出这个数就能求得询问的答案（唯一的区别是题目中相同的 b 是无标号的，而我们求的是有标号的），并且这里的转化可以通过类似预处理前缀积的形式做到 O(n)−O(1)。
先考虑能不能单组询问 O(n) 求出答案。下文令 pi 表示最大的下标 x 使得 bx≤i。
考虑从右向左寻找每一个 ai 的匹配，对于 i=r 来说，它可以选的是匹配是 b 中区间内所有 ≥ar 的数，也就是说这一位的方案数是 r−max(l−1,par−1)。
再来考虑 [l,r−1] 的区间内的匹配，容易发现这一部分的方案数恰好与直接询问 [l,r−1] 的匹配数相等。
所以我们可以知道，对于一组询问，匹配数应当是 i=l∏ri−max(l−1,pai−1)。
这样我们就可以单组询问 O(n) 求出匹配数。
这个时候我们发现，由于数组 a,b 都有序，那么一定存在一个位置 w(l−1≤w≤r) 满足对于所有 i∈[l,w]，都有上述式子的 max 取到 l−1，对于所有 i∈(w,r] 都有上述式子的 max 取到 pai−1，并且 w 容易 O(1) 求出。
那么对于 i∈[l,w] 的部分，贡献是一个阶乘；对于剩下的部分，可以直接前缀积求。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mod=998244353;
ll p[200001],ip[200001];
ll L[200001],iL[200001];
ll jc[200001];
ll ijc[200001];
ll inv[200001];
int ar[200001];
int br[200001];
int a[200001];
int b[200001];
int n,m;
inline ll qow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
inline void init()
{
jc[0]=1;
for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
ijc[n]=qow(jc[n],mod-2);
for(int i=n;i;i--)
{
ijc[i-1]=ijc[i]*i%mod;
inv[i]=ijc[i]*jc[i-1]%mod;
}
for(int i=1;i<=n;i++)
{
ar[i]=ar[i-1],br[i]=br[i-1];
while(ar[i]<n&&a[ar[i]+1]<=i) ar[i]++;
while(br[i]<n&&b[br[i]+1]<=i) br[i]++;
}
p[0]=ip[0]=1;
for(int i=1;i<=n;i++)
{
int th=i-br[a[i]-1];
p[i]=p[i-1]*th%mod;
ip[i]=ip[i-1]*inv[th]%mod;
}
int cnt=0;L[0]=iL[0]=1;
for(int i=1;i<=n;i++)
{
if(b[i]!=b[i-1]) cnt=0;
cnt++;
L[i]=L[i-1]*inv[cnt]%mod;
iL[i]=iL[i-1]*cnt%mod;
}
}
inline ll get(int l,int r)
{
if(b[l]==b[r]) return ijc[r-l+1];
int w1=br[b[l]],w2=br[b[r]-1]+1;
return ijc[w1-l+1]*ijc[r-w2+1]%mod*L[w2-1]%mod*iL[w1]%mod;
}
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read();
init();
m=read();
for(int i=1;i<=m;i++)
{
int l=read(),r=read();ll val;
if(a[r]<=b[l]) val=jc[r-l+1];
else
{
int w=ar[b[l]];
val=jc[w-l+1]*ip[w]%mod*p[r]%mod;
}
printf("%lld\n",val*get(l,r)%mod);
}
return 0;
}
T4 云顶之弈
考虑 n=1 的时候怎么做，令 fpi,0 表示前 i 个牌的权值总和，fpi,1∼5 表示前 i 个牌，最后要留下 1∼5 张 A 的权值总和（不算留的几张），fpi,6∼10 表示前 i 个牌，最后留下 1∼5 张 B 的权值总和（不算留的几张）。
同理使用 dpi,0∼10 表示方案数。
考虑如何转移，以第 i 张牌是 A 时 fp 的转移为例。
首先，第 i 张牌可以丢掉，有 fpi,j←fpi−1,j。
第 i 张牌还可以和之前的一些 A 一起留着，对于 j<5 有 fpi,j←fpi−1,j−1。
第 i 张牌还可以和之前的一些 A 一起合成一张大牌，有：$fp_{i,0}\gets fp_{i-1,0}+dp_{i-1,0}A+fp_{i-1,2}+dp_{i-1,2}B+fp_{i-1,5}+dp_{i-1,5}C$。
dp 的转移差不多，第 i 张牌是 a 的转移也类似。
这样就解决了 n=1 的问题。
n=1 的时候，瓶颈在于操作 3。考虑使用链表维护序列，使用矩阵维护上述操作。
操作 3 就是矩阵乘法然后合并链表，操作 1 就是矩阵乘法然后链表插入一个元素。
操作 2 就是链表删除一个元素，然后乘一个转移矩阵的逆。
这样做显然是对的，但是由于要同时维护方案数和权值和，你会发现矩阵是 22×22 的，这很孬。
考虑把 dp 和 fp 分开维护，你会发现这俩拆成两个矩阵也是可以维护的，这样就只需要维护两个 11×11 的矩阵。
时间复杂度 O((Q+∑ki)L3)，其中 L=11 为矩阵大小。
# T1 聪明的质检员
就是，我们考虑这样一个$dp$。
$dp_{l,r}$表示当前我知道不合格品在$[l,r]$区间内，我有多大的概率算出来答案。
那么$dp_{1,n}$就是我要的结果了。
那么，对于$[l,r]$来说，首先我有$\frac{1}{r-l+1}$的概率直接找到答案。
其次，有$lef=\frac{mid-l+1}{r-l+1},rig=1-lef-\frac{1}{r-l+1}$的概率不合格品在左边/右边。
而后续找到的前提条件是，我们得到了正确的提示：
也就是：$ P=\sum_{i=\frac{k+1}{2}}^kC_k^ip^i(1-p)^{k-i} $的概率得到正确的提示。
所以答案就是：
$dp_{l,r}=\frac{1}{r-l+1}+lef\times P\times dp_{l,mid}+rig\times P\times dp_{mid+1,r}$。
很显然地：我们只关心$r-l$的大小，所以直接用$dp_{len}$来算即可。
由于当$len$是奇数的时候只会递归到两个一样的$dp_{\frac{len}{2}}$，$len$是偶数的时候会递归到一个$dp_{\frac{len}{2}}$和一个$dp_{\frac{len}{2}-1}$。容易发现有用的状态只有$O(logn)$种。
```c++
#include <bits/stdc++.h>
#define ll long long
#define maxn 200005
#define eps -1e-8
using namespace std;
map<ll,double> f;
double p,dui;
ll n,k;
ll C[15][15];
double dfs(ll n)
{
if (n<=2) return f[n]=1.0;
if (f.count(n)) return f[n];
ll lef,rig;
if (n&1) lef=rig=n/2; else lef=n/2-1,rig=n/2;
double zuo=1.0/n*lef,you=1.0/n*rig; //在左边的概率，在右边的概率
f[n]+=1.0/n;
f[n]+=dui*dfs(lef)*zuo+dui*dfs(rig)*you;
return f[n];
}
int main()
{
C[0][0]=1;
for (int i=1;i<=11;i++)
for (int j=0;j<=i;j++)
{
if (j==0 || i==1) C[i][j]=1; else C[i][j]=C[i-1][j]+C[i-1][j-1];
}
cin>>n>>p>>k;
for (int i=k/2+1;i<=k;i++)
{
double gai=1;
for (int j=1;j<=i;j++) gai*=p;
for (int j=1;j<=k-i;j++) gai*=(1-p);
gai*=C[k][i];
dui+=gai;
}
dfs(n);
printf("%.4lf\n",f[n]);
}
```
# T2 乒乓球
source：某个CF题改编的简单版本。
30分的小数据模拟起来还是很简单的，不多说。
对于一条链，是在提示正解的：
我们考虑开个线段树维护一下区间内从`0:0,1:0,0:1,1:1`分别开始模拟一轮，一轮以后比分差是多少，小分是多少。
比如
`0:0`开始模拟一轮以后，比分差是$1$，小分是`1:1`。
`1:0`开始模拟一轮以后，比分差是$-1$，小分是`0:1`。
`0:1`开始模拟一轮以后，比分差是$0$，小分是`1:1`。
`1:1`开始模拟一轮以后，比分差是$1$，小分是`1:0`。
那么，从大的层面上来说，每一轮就会陷入：`0:0`->`1:1`->`1:0`->`0:1`->`1:1`->...的循环，在这个循环内的比分是$1+-1+0=0$，所以是平局。
那么正解就很简单了，我直接上树剖或者树上倍增，就可以维护好这个东西。
纯粹就是个小模拟，复杂度$O(nlog^2n)$。
```c++
#include<bits/stdc++.h>
#define maxn 200005
#define ll long long
using namespace std;
//0 1 2 3
//0:0 1:0 0:1 1:1
struct nod{
int sta[4],score[4];
};
nod val[3];
nod init(int f)
{
nod ret;
if (f==1)
{
ret.sta[0]=1; ret.sta[1]=0; ret.sta[2]=3; ret.sta[3]=0;
ret.score[0]=0; ret.score[1]=1; ret.score[2]=0; ret.score[3]=1;
}
else if (f==0)
{
ret.sta[0]=2; ret.sta[1]=3; ret.sta[2]=0; ret.sta[3]=0;
ret.score[0]=0; ret.score[1]=0; ret.score[2]=-1; ret.score[3]=-1;
}
else
{
for (int i=0;i<=3;i++) ret.sta[i]=i,ret.score[i]=0;
}
return ret;
}
nod merge(nod x,nod y)
{
nod ret;
for (int fir=0;fir<=3;fir++)
{
int score=0;
int now=fir;
score+=x.score[now]; now=x.sta[now];
score+=y.score[now]; now=y.sta[now];
ret.score[fir]=score; ret.sta[fir]=now;
}
return ret;
}
int n,Q;
int u,v,w;
basic_string<int> edge[maxn];
int fa[maxn][21],dep[maxn];
//F表示从你向上，G表示从父亲到你
nod F[maxn][21],G[maxn][21];
void dfs(int x,int father,int v)
{
dep[x]=dep[father]+1;
fa[x][0]=father; for (int i=1;i<=19;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
F[x][0]=val[v]; G[x][0]=val[v];
for (int i=1;i<=19;i++)
{
F[x][i]=merge(F[x][i-1],F[fa[x][i-1]][i-1]);
G[x][i]=merge(G[fa[x][i-1]][i-1],G[x][i-1]);
}
for (int y:edge[x])
{
int id=abs(y),tag=(y<0?1:0);
if (id!=father) dfs(id,x,tag);
}
}
void out(nod x)
{
for (int i=0;i<=3;i++) cout<<x.sta[i]<<" "<<x.score[i]<<endl;
}
int mem[4];
void check(nod x)
{
mem[0]=0; mem[1]=mem[2]=mem[3]=1<<29;
int now=0,score=0;
while (true)
{
score+=x.score[now]; now=x.sta[now];
if (mem[now]!=(1<<29))
{
int cha=score-mem[now];
if (cha>0) cout<<"Win\n";
if (cha==0) cout<<"Draw\n";
if (cha<0) cout<<"Lose\n";
return;
}
mem[now]=score;
}
return;
}
void work(int u,int v)
{
nod a=val[2],b=val[2];
int cha=dep[u]-dep[v];
if (cha>0)
{
for (int i=19;i>=0;i--)
if ((cha>>i)&1)
{
a=merge(a,F[u][i]);
u=fa[u][i];
}
}
else if (cha<0)
{
cha=-cha;
for (int i=19;i>=0;i--)
if ((cha>>i)&1)
{
b=merge(G[v][i],b);
v=fa[v][i];
}
}
if (u==v) {check(merge(a,b)); return;}
for (int i=19;i>=0;i--)
if (fa[u][i]!=fa[v][i])
{
a=merge(a,F[u][i]); u=fa[u][i];
b=merge(G[v][i],b); v=fa[v][i];
}
a=merge(a,F[u][0]); u=fa[u][0];
b=merge(G[v][0],b); v=fa[v][0];
check(merge(a,b));
return;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
val[0]=init(0); val[1]=init(1); val[2]=init(2);
cin>>n;
for (int i=1;i<n;i++)
{
cin>>u>>v>>w;
if (w==0) edge[u]+=v,edge[v]+=u;
else edge[u]+=-v,edge[v]+=-u;
}
dfs(1,1,2);
cin>>Q;
while (Q--)
{
cin>>u>>v;
work(u,v);
}
}
```
# T3 田忌赛马
bonus：有一个神秘的不依赖随机数据的莫队做法，见WYR的题解。
source：瞎编的。
首先，我们可以把星粉剂想象成，每次可以给一个数字$+1$。
45分：
我们考虑一下询问的区间$a,b$里面分别有多少个$1,2,3,...,n$。
假设$\leq 5$的$a_i$有$x$个，$\leq 4$的$b_i$有$y$个，那么显然：有$x-y$个$\leq 5$的数字要变得$\geq 5$，假设$=5$的$b_i$有$z$个，那么：我们需要从$x-y$个数字中，挑选$x-y-z$个变得$\geq 6$。
我们设$A_i$表示$a$数组中有多少个$\leq i$的数字，$B_i$表示$b$数组中有多少个$\leq i$的数字，那么：
$\prod _{i=1}^{mx}C_{A_i-B_{i-1}}^{A_{i}-B_{i}}$
就是答案了。
那么对于$mx\leq 1000$的小数据，我们直接暴力求出$A,B$数组即可。注意一个细节是如果你数组开了$2\times 2e5\times 1000$，会喜提`MLE`。
100分：
这个好容易想到的其实。
这是随机数据诶，随机数据性质多多。
我们对于每次$l_i,r_i$，从$a_{l_i},b_{r_i}$分别向右/向左暴力，一旦遇到一个位置算出来的系数跟$A_i,B_i$一样，就说明中间这一段都一样，直接用之前的答案就好了。
至于维护区间里有多少个范围内的数字，直接用主席树即可（实际上这个过程可以只在一开始主席树查一遍，之后的询问直接在这个基础上指针跑一跑就可以线性了）。
时间复杂度在随机数据下是：$O(nlogn+kQlogn)$。
可以通过上述优化把复杂度变成：$O(nlogn+kQ+Qlogn)$，这样就能卡掉莫队了。
```c++
#include<bits/stdc++.h>
#define maxn 200005
#define ls lson[now]
#define rs rson[now]
#define mid ((l+r)>>1)
#define ll long long
#define mod 998244353
using namespace std;
ll pw(ll x,ll mi)
{
ll ret=1;
while (mi)
{
if (mi&1) ret=ret*x%mod;
mi=mi>>1; x=x*x%mod;
}
return ret;
}
ll fac[maxn],inv[maxn],ni[maxn];
ll cc(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
void init2(int zd)
{
ni[0]=ni[1]=1;
for (int i=2;i<=zd;i++) ni[i]=(mod-(mod/i)*ni[mod%i]%mod);
fac[0]=fac[1]=inv[0]=1;
for (int i=2;i<=zd;i++) fac[i]=fac[i-1]*i%mod;
inv[zd]=pw(fac[zd],mod-2);
for (int i=zd-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
return;
}
int rt1[maxn],rt2[maxn],tot=0;
int sum[maxn<<6],lson[maxn<<6],rson[maxn<<6];
ll a[maxn],b[maxn];
ll ans[maxn];
ll x[maxn],y[maxn];
int n;
int tx[maxn],ty[maxn];
void ins(int &now,int pre,int l,int r,int id)
{
if (!now) now=++tot;
if (l==r) {sum[now]=sum[pre]+1; return;}
if (id<=mid) {ins(lson[now],lson[pre],l,mid,id); rson[now]=rson[pre];}
else {ins(rson[now],rson[pre],mid+1,r,id); lson[now]=lson[pre];}
sum[now]=sum[lson[now]]+sum[rson[now]];
}
int query(int now,int l,int r,int L,int R)
{
if (!now || L>R) return 0;
if (L<=l && r<=R) return sum[now];
int ret=0;
if (L<=mid) ret+=query(lson[now],l,mid,L,R);
if (mid+1<=R) ret+=query(rson[now],mid+1,r,L,R);
return ret;
}
void out(int l,int r,int *a)
{
for (int i=l;i<=r;i++) cout<<a[i]<<" "; cout<<endl;
}
void work(int l,int r)
{
ll ret=1,L=-1,R=-1;
for (int i=a[l];i<=b[r];i++)
{
int shang=query(rt1[r],1,n,1,i)-query(rt1[l-1],1,n,1,i);
int xia=query(rt2[r],1,n,1,i-1)-query(rt2[l-1],1,n,1,i-1);
int xia2=query(rt2[r],1,n,1,i)-query(rt2[l-1],1,n,1,i);
tx[i]=shang-xia; //一共还剩这么多数字
ty[i]=shang-xia2; //要搬这么多数字走
ret=ret*cc(tx[i],ty[i])%mod;
if (tx[i]==x[i] && ty[i]==y[i]) {L=i; break;}
}
if (L==-1) {cout<<ret<<"\n"; return;} //两端碰撞了
for (int i=b[r];i>L;i--)
{
int shang=query(rt1[r],1,n,1,i)-query(rt1[l-1],1,n,1,i);
int xia=query(rt2[r],1,n,1,i-1)-query(rt2[l-1],1,n,1,i-1);
int xia2=query(rt2[r],1,n,1,i)-query(rt2[l-1],1,n,1,i);
tx[i]=shang-xia; //一共还剩这么多数字
ty[i]=shang-xia2; //要搬这么多数字走
ret=ret*cc(tx[i],ty[i])%mod;
if (tx[i]==x[i] && ty[i]==y[i]) {R=i; break;}
}
if (R==-1 || R==L+1) {cout<<ret<<"\n"; return;} //两端碰撞了
//还要乘上L+1~R-1
ret=ret*pw(ans[L],mod-2)%mod*ans[R-1]%mod;
cout<<ret<<"\n";
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
init2(200000);
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++) cin>>b[i];
for (int i=1;i<=n;i++)
{
ins(rt1[i],rt1[i-1],1,n,a[i]);
ins(rt2[i],rt2[i-1],1,n,b[i]);
}
//搞定初始的答案
for (int i=1;i<=n;i++)
{
int shang=query(rt1[n],1,n,1,i);
int xia=query(rt2[n],1,n,1,i-1),xia2=query(rt2[n],1,n,1,i);
x[i]=shang-xia; //一共还剩这么多数字
y[i]=shang-xia2; //要搬这么多数字走
}
ans[0]=1;
for (int i=1;i<=n;i++) ans[i]=ans[i-1]*cc(x[i],y[i])%mod;
int Q; cin>>Q;
// for (int i=1;i<=b[n];i++) cout<<x[i]<<" "; cout<<endl;
// for (int i=1;i<=b[n];i++) cout<<y[i]<<" "; cout<<endl;
int l,r;
while (Q--)
{
cin>>l>>r;
work(l,r);
}
}
```
这是一个不依赖数据随机的 $O(n+q)$ 做法。
考虑先求出两个数组匹配的方案数，满足任意一组匹配 $(x,y)$ 都有 $a_x\le b_y$。
容易发现求出这个数就能求得询问的答案（唯一的区别是题目中相同的 $b$ 是无标号的，而我们求的是有标号的），并且这里的转化可以通过类似预处理前缀积的形式做到 $O(n)-O(1)$。
先考虑能不能单组询问 $O(n)$ 求出答案。下文令 $p_i$ 表示最大的下标 $x$ 使得 $b_x\le i$。
考虑从右向左寻找每一个 $a_i$ 的匹配，对于 $i=r$ 来说，它可以选的是匹配是 $b$ 中区间内所有 $\ge a_r$ 的数，也就是说这一位的方案数是 $r-\max(l-1,p_{a_r-1})$。
再来考虑 $[l,r-1]$ 的区间内的匹配，容易发现这一部分的方案数恰好与直接询问 $[l,r-1]$ 的匹配数相等。
所以我们可以知道，对于一组询问，匹配数应当是 $\prod\limits_{i=l}^ri-\max(l-1,p_{a_i-1})$。
这样我们就可以单组询问 $O(n)$ 求出匹配数。
这个时候我们发现，由于数组 $a,b$ 都有序，那么一定存在一个位置 $w(l-1\le w\le r)$ 满足对于所有 $i\in[l,w]$，都有上述式子的 $\max$ 取到 $l-1$，对于所有 $i\in(w,r]$ 都有上述式子的 $\max$ 取到 $p_{a_i-1}$，并且 $w$ 容易 $O(1)$ 求出。
那么对于 $i\in[l,w]$ 的部分，贡献是一个阶乘；对于剩下的部分，可以直接前缀积求。
```c++
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mod=998244353;
ll p[200001],ip[200001];
ll L[200001],iL[200001];
ll jc[200001];
ll ijc[200001];
ll inv[200001];
int ar[200001];
int br[200001];
int a[200001];
int b[200001];
int n,m;
inline ll qow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
inline void init()
{
jc[0]=1;
for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
ijc[n]=qow(jc[n],mod-2);
for(int i=n;i;i--)
{
ijc[i-1]=ijc[i]*i%mod;
inv[i]=ijc[i]*jc[i-1]%mod;
}
for(int i=1;i<=n;i++)
{
ar[i]=ar[i-1],br[i]=br[i-1];
while(ar[i]<n&&a[ar[i]+1]<=i) ar[i]++;
while(br[i]<n&&b[br[i]+1]<=i) br[i]++;
}
p[0]=ip[0]=1;
for(int i=1;i<=n;i++)
{
int th=i-br[a[i]-1];
p[i]=p[i-1]*th%mod;
ip[i]=ip[i-1]*inv[th]%mod;
}
int cnt=0;L[0]=iL[0]=1;
for(int i=1;i<=n;i++)
{
if(b[i]!=b[i-1]) cnt=0;
cnt++;
L[i]=L[i-1]*inv[cnt]%mod;
iL[i]=iL[i-1]*cnt%mod;
}
}
inline ll get(int l,int r)
{
if(b[l]==b[r]) return ijc[r-l+1];
int w1=br[b[l]],w2=br[b[r]-1]+1;
return ijc[w1-l+1]*ijc[r-w2+1]%mod*L[w2-1]%mod*iL[w1]%mod;
}
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read();
init();
m=read();
for(int i=1;i<=m;i++)
{
int l=read(),r=read();ll val;
if(a[r]<=b[l]) val=jc[r-l+1];
else
{
int w=ar[b[l]];
val=jc[w-l+1]*ip[w]%mod*p[r]%mod;
}
printf("%lld\n",val*get(l,r)%mod);
}
return 0;
}
```
# T4 云顶之弈
考虑 $n=1$ 的时候怎么做，令 $fp_{i,0}$ 表示前 $i$ 个牌的权值总和，$fp_{i,1\sim 5}$ 表示前 $i$ 个牌，最后要留下 $1\sim 5$ 张 `A` 的权值总和（不算留的几张），$fp_{i,6\sim 10}$ 表示前 $i$ 个牌，最后留下 $1\sim 5$ 张 `B` 的权值总和（不算留的几张）。
同理使用 $dp_{i,0\sim 10}$ 表示方案数。
考虑如何转移，以第 $i$ 张牌是 `A` 时 $fp$ 的转移为例。
首先，第 $i$ 张牌可以丢掉，有 $fp_{i,j}\gets fp_{i-1,j}$。
第 $i$ 张牌还可以和之前的一些 `A` 一起留着，对于 $j<5$ 有 $fp_{i,j}\gets fp_{i-1,j-1}$。
第 $i$ 张牌还可以和之前的一些 `A` 一起合成一张大牌，有：$fp_{i,0}\gets fp_{i-1,0}+dp_{i-1,0}A+fp_{i-1,2}+dp_{i-1,2}B+fp_{i-1,5}+dp_{i-1,5}C$。
$dp$ 的转移差不多，第 $i$ 张牌是 `a` 的转移也类似。
这样就解决了 $n=1$ 的问题。
$n\ne 1$ 的时候，瓶颈在于操作 $3$。考虑使用链表维护序列，使用矩阵维护上述操作。
操作 $3$ 就是矩阵乘法然后合并链表，操作 $1$ 就是矩阵乘法然后链表插入一个元素。
操作 $2$ 就是链表删除一个元素，然后乘一个转移矩阵的逆。
这样做显然是对的，但是由于要同时维护方案数和权值和，你会发现矩阵是 $22\times 22$ 的，这很孬。
考虑把 $dp$ 和 $fp$ 分开维护，你会发现这俩拆成两个矩阵也是可以维护的，这样就只需要维护两个 $11\times 11$ 的矩阵。
时间复杂度 $O((Q+\sum k_i)L^3)$，其中 $L=11$ 为矩阵大小。
