P17171 现在

题目分析

定义 \(\operatorname{f}(B)\) 为对排列 \(B\) 执行一轮从左到右的冒泡操作（若 \(B_i>B_{i+1}\) 则交换，否则不操作）。\(\operatorname{cnt}(A)=\#\{B\mid\operatorname{f}(B)=A\}\)，即有多少个排列 \(B\) 经过一轮冒泡后恰好变成 \(A\)。要求统计字典序在 \([P,Q]\) 内且 \(\operatorname{cnt}(A)\in[L,R]\) 的排列 \(A\) 的数量，答案对 \(998244353\) 取模。

核心思路

1. \(\operatorname{f}\) 的性质：最大值归尾

观察 \(\operatorname{f}\) 的操作过程：从左到右扫描，遇到逆序对 \(B_i>B_{i+1}\) 就交换。由于 \(N\) 是最大值，它所在的任何位置 \(B_i=N\) 都满足 \(B_i>B_{i+1}\)，因此 \(N\) 会被不断向右交换，直到到达末尾。

结论：\(\operatorname{f}(B)\) 的最后一个元素必定是 \(N\)。因此：

• 若 \(A_N\ne N\)，则 \(\operatorname{cnt}(A)=0\)，不存在任何 \(B\) 使得 \(\operatorname{f}(B)=A\)。
• 若 \(A_N=N\)，则需要进一步分析。

2. \(\operatorname{cnt}(A)=2^{m-1}\) 的证明

设 \(A\) 是一个以 \(N\) 结尾的排列，\(m\) 为 \(A\) 中左到右最大值（record / left-to-right maximum）的个数。即 \(m=\#\{i\mid A_i>\max(A_1,\dots,A_{i-1})\}\)。

逆向构造：给定 \(A=\operatorname{f}(B)\)，我们需要逆向还原出所有可能的 \(B\)。

考虑 \(\operatorname{f}\) 的逆过程。在正向操作中，\(N\) 从其初始位置一路向右冒泡到末尾。\(N\) 之外的其他元素，只有在与 \(N\) 相邻交换时才会改变相对位置，且每个元素最多被 \(N\) 交换一次（\(N\) 只往右走）。

考虑 \(A\) 中的左到右最大值序列 \(r_1<r_2<\dots<r_m=N\)。在 \(\operatorname{f}\) 之前，\(N\) 从某个位置出发向右冒泡。每经过一个左到右最大值 \(r_j\)（\(j<m\)），\(N\) 会与其交换，使 \(r_j\) 向左移动一位。关键在于：\(r_j\) 可以选择与 \(N\) 交换（出现在 \(B\) 中 \(N\) 的左边），也可以选择不交换——但这取决于 \(B\) 中 \(r_j\) 和 \(N\) 的相对位置。

更精确地说，对于每个非首位的左到右最大值 \(r_j\)（\(j=2,3,\dots,m\)），在原排列 \(B\) 中存在一个二元选择：\(r_j\) 是否紧邻在 \(N\) 之前（即 \(B\) 中 \(r_j\) 排在 \(N\) 前一格）。这个选择是独立的，因此共有 \(2^{m-1}\) 种不同的 \(B\)。

结论：\(\operatorname{cnt}(A)=2^{m-1}\)（当 \(A_N=N\)），其中 \(m\) 为左到右最大值个数。

3. 条件转化

\(L\le\operatorname{cnt}(A)\le R\) 等价于：

• 若 \(A_N\ne N\)：\(\operatorname{cnt}(A)=0\)，需 \(L=0\)。
• 若 \(A_N=N\)：\(L\le 2^{m-1}\le R\)，即 \(m\in[m_{\min},m_{\max}]\)，其中：
  • \(m_{\min}=\lceil\log_2 L\rceil+1\)（\(L>0\) 时），\(L=0\) 时 \(m_{\min}=1\)。
  • \(m_{\max}=\lfloor\log_2 R\rfloor+1\)。

由于 \(R\le10^{18}<2^{60}\)，故 \(m_{\max}\le 61\)，这是一个非常小的常数。

4. 第一类 Stirling 数与左到右最大值

排列的左到右最大值个数等于其循环个数（由 Foata 变换给出双射）。\(n\) 元排列中恰好有 \(k\) 个循环的排列数为无符号第一类 Stirling 数 \(c(n,k)\)，满足递推：

\[c(n,k)=c(n-1,k-1)+(n-1)\cdot c(n-1,k) \]

这一转化使得我们可以利用 Stirling 数的性质来计数。

5. 数位 DP 计数

设 \(\operatorname{cnt\_less}(X)\) 表示字典序严格小于 \(X\)，满足 \(A_N=N\) 且左到右最大值数 \(m\in[m_{\min},m_{\max}]\) 的排列数。

使用树状数组维护尚未使用的值集合，逐位确定 \(A\) 的值。在第 \(i\) 位（\(1\le i\le N\)），设已确定前 \(i-1\) 位的值，当前最大值为 \(\mathit{cm}\)，已有 \(\mathit{cr}\) 个左到右最大值。考虑放置 \(v<X_i\)：

剩余 \(k=N-i\) 个位置中，最后一位必须放 \(N\)，故实际只有 \(k-1\) 个自由位置。设这 \(k-1\) 个位置要填入 \(t\) 个值（从剩余未用的值中选取，排除 \(N\)），其中 \(t\) 个值大于 \(\mathit{cm}\)。这些大于 \(\mathit{cm}\) 的值会产生新的左到右最大值。设它们贡献 \(a\) 个循环，则需 \(a\in[m_{\min}-\mathit{cr}-\Delta,m_{\max}-\mathit{cr}-\Delta]\)（\(\Delta\) 取决于 \(v\) 是否为新的左到右最大值）。

方案数为：

\[\binom{k-1}{t}\cdot(k-1-t)!\cdot\sum_{a}c(t,a)=\frac{(k-1)!}{t!}\cdot\sum_a c(t,a) \]

分两种情况讨论 \(v\) 的选择：

• 情况一（\(v<\mathit{cm}\)，不产生新记录）：\(v\) 本身不增加左到右最大值数，\(t\) 固定（取决于未使用的大于 \(\mathit{cm}\) 的值个数）。直接用上式计算。
• 情况二（\(v>\mathit{cm}\)，产生新记录）：\(v\) 本身贡献一个新的左到右最大值，且 \(t\) 随 \(v\) 的选取而变化（\(v\) 越大，\(t\) 越小）。需要对 \(v\) 遍历求和。

6. PS 前缀和数组加速

对于情况二，\(t\) 随 \(v\) 变化，直接遍历 \(v\) 的复杂度为 \(O(N)\)，总体 \(O(N^2)\)，无法接受。

定义前缀和数组：

\[\operatorname{PS}[a][t]=\sum_{j=0}^{t}\frac{\operatorname{pref\_c}[j][a]}{j!} \]

其中 \(\operatorname{pref\_c}[j][a]=\sum_{i=0}^{a}c(j,i)\) 为 Stirling 数的前缀和。

利用 \(\operatorname{PS}\)，可以将对 \(t\) 的求和转化为 \(O(1)\) 的前缀差：

\[\sum_{t=L}^{R}\frac{\operatorname{pref\_c}[t][a]}{t!}=\operatorname{PS}[a][R]-\operatorname{PS}[a][L-1] \]

对于情况二，\(t\) 的取值范围为 \([L_m, R_m]\)，其中 \(L_m\) 和 \(R_m\) 由未使用值集合决定。需要按 \(t\le r_{\max}\)（最大允许循环数）与 \(t>r_{\max}\) 分段：

• 第一段（\(t\le r_{\max}\)）：所有 \(a\) 值都合法，贡献为 \(\sum_{t=L_m}^{\min(R_m,r_{\max})}\frac{1}{t!}\) 的项数减去 \(\operatorname{PS}\) 的前缀差。
• 第二段（\(t>r_{\max}\)）：只有 \(a\le r_{\max}\) 合法，贡献为 \(\operatorname{PS}[r_{\max}]\) 与 \(\operatorname{PS}[a_{\min}-1]\) 的前缀差。

每段均可在 \(O(1)\) 时间内完成计算，因此 \(\operatorname{cnt\_less}\) 的总复杂度为 \(O(N\log N)\)（树状数组）。

7. \(L=0\) 的处理

当 \(L=0\) 时，\(\operatorname{cnt}(A)=0\) 的排列（即 \(A_N\ne N\)）也合法，需要额外计入。采用容斥：

\[\operatorname{ans}=\underbrace{(\text{区间内所有排列})}_{\text{无约束}}-\underbrace{(\text{区间内}A_N{=}N\text{的排列})}_{\text{cnt}>0\text{的排列}}+\underbrace{(\text{区间内}A_N{=}N\text{且}m\le m_{\max}\text{的排列})}_{\text{cnt}\le R\text{的排列}} \]

其中：

• "所有排列"用 \(\operatorname{cnt\_all}(X)\) 统计，即标准数位 DP：第 \(i\) 位放 \(v<X_i\)，剩余 \(k\) 位自由排列，贡献 \(\binom{\text{未用}}{1}\cdot k!\)。
• "\(A_N=N\) 的排列"用 \(\operatorname{cnt\_N}(X)\) 统计，类似数位 DP 但约束末位为 \(N\)，中间不能选 \(N\)。

8. Q 本身的判定

由于 \(\operatorname{cnt\_less}\) 统计的是严格小于 \(X\) 的排列，而题目要求 \([P,Q]\) 闭区间，需单独判定 \(Q\) 本身是否合法：

• 检查 \(Q_N=N\)；
• 计算 \(Q\) 的左到右最大值数 \(m\)；
• 检查 \(m\in[m_{\min},m_{\max}]\)（或 \(L=0\) 时 \(m\le m_{\max}\)）。

若合法则答案加 \(1\)。

复杂度分析

• 预处理 \(\operatorname{calcPS}\)：\(O(NK)\)，其中 \(K\le 62\)。
• 每次 \(\operatorname{cnt\_less}\)：\(O(N\log N)\)（树状数组）。
• \(\operatorname{cnt\_all}\)/\(\operatorname{cnt\_N}\)：\(O(N\log N)\)。
• 总时间：\(O(NK+N\log N)\)，\(N=10^6\) 时约 \(1\text{s}\)。
• 空间：\(O(NK)\)，即 PS 数组约 \(62\times10^6\times4\text{B}\approx248\text{MB}\)。

代码

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int N,K,mn,mx;
long long L,R;
int P[1000010],Q[1000010],fac[1000010],inv[1000010],fw[1000010];
int *PS,cc[70],cn[70],pc[70];
void fw_add(int i,int d){while(i<=N)fw[i]+=d,i+=i&-i;return ;}
int fw_sum(int i){if(i<=0)return 0;if(i>N)i=N;int s=0;while(i>0)s+=fw[i],i-=i&-i;return s;}
void fw_init(){memset(fw,0,sizeof(int)*(N+2));for(int v=1;v<=N;v++)fw_add(v,1);return ;}
int add(int a,int b){a+=b;if(a>=MOD)a-=MOD;return a;}
int sub(int a,int b){a-=b;if(a<0)a+=MOD;return a;}
int mul(int a,int b){return (long long)a*b%MOD;}
int pw(int a,int b){int r=1;while(b){if(b&1)r=mul(r,a);a=mul(a,a),b>>=1;}return r;}
int getPS(int a,int t){if(a<0||t<0)return 0;if(a>K)a=K;if(t>N-1)t=N-1;return PS[a*N+t];}
void calcPS(){memset(cc,0,sizeof(cc)),cc[0]=1;for(int a=0;a<=K;a++)pc[a]=1,PS[a*N]=mul(inv[0],pc[a]);for(int t=1;t<N;t++){memset(cn,0,sizeof(cn));int ma=min(t,K),c=t-1;for(int a=1;a<=ma;a++)cn[a]=add(cc[a-1],mul(c,cc[a]));pc[0]=cn[0];for(int a=1;a<=K;a++)pc[a]=add(pc[a-1],cn[a]);for(int a=0;a<=K;a++)PS[a*N+t]=add(PS[a*N+t-1],mul(inv[t],pc[a]));memcpy(cc,cn,sizeof(cc));}return ;
}
int cnt_all(int*X){int ans=0;fw_init();for(int i=1;i<=N;i++){int xi=X[i-1],k=N-i,c=fw_sum(xi-1);if(c>0)ans=add(ans,mul(c,fac[k]));if(fw_sum(xi)-fw_sum(xi-1)==0)break;fw_add(xi,-1);}return ans;
}
int cnt_N(int*X){int ans=0;fw_init();for(int i=1;i<=N;i++){int xi=X[i-1],k=N-i;if(k==0)break;int c=fw_sum(xi-1);if(c>0&&N<=xi-1)c--;if(c>0)ans=add(ans,mul(c,fac[k-1]));if(fw_sum(xi)-fw_sum(xi-1)==0)break;if(xi==N&&i<N)break;fw_add(xi,-1);}return ans;
}
int cnt_less(int*X){if(mn>mx)return 0;int ans=0,cm=0,cr=0;fw_init();for(int i=1;i<=N;i++){int xi=X[i-1],k=N-i;if(k==0){if(xi>N&&fw_sum(N)>0){int nr=cr+(N>cm?1:0);if(mn<=nr&&nr<=mx)ans=add(ans,1);}break;}int l2=min(xi-1,cm-1);if(l2>=1){int c2=fw_sum(l2);if(c2>0){int t0=fw_sum(N)-fw_sum(cm);if(N>cm)t0--;if(t0>=0){int am=max(0,mn-cr-1),ax=min(mx-cr-1,t0);if(am<=ax){int t1=sub(getPS(ax,t0),getPS(ax,t0-1));int t2=sub(getPS(am-1,t0),getPS(am-1,t0-1));ans=add(ans,mul(c2,mul(fac[k-1],sub(t1,t2))));}}}}if(xi-1>cm){int c1=fw_sum(xi-1)-fw_sum(cm);if(c1>0){int m=fw_sum(N)-fw_sum(cm);if(N>cm)m--;if(m>0){int Lm=m-c1,Rm=m-1;int am=max(0,mn-cr-2),rm=mx-cr-2;if(am<=rm){int p1=0,p2=0;if(Lm<=rm){int c1v=min(Rm,rm)-Lm+1,si=0;if(am>0)si=sub(getPS(am-1,min(Rm,rm)),getPS(am-1,Lm-1));p1=sub(c1v%MOD,si);}int L2=max(Lm,rm+1);if(L2<=Rm){int sr=sub(getPS(rm,Rm),getPS(rm,L2-1)),sa=0;if(am>0)sa=sub(getPS(am-1,Rm),getPS(am-1,L2-1));p2=sub(sr,sa);}ans=add(ans,mul(fac[k-1],add(p1,p2)));}}}}if(xi>N||fw_sum(xi)-fw_sum(xi-1)==0)break;if(xi==N&&i<N)break;fw_add(xi,-1);if(xi>cm)cr++,cm=xi;}return ans;
}
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>N>>L>>R;for(int i=0;i<N;i++)cin>>P[i];for(int i=0;i<N;i++)cin>>Q[i];mn=1,mx=N;if(L>0){while(mn<=61&&(1LL<<(mn-1))<L)mn++;if(mn>61){cout<<0<<"\n";return ( 0 - 0 );}}if(R<(1LL<<60)){mx=1;while(mx<=61&&(1LL<<(mx-1))<=R)mx++;mx--,mx=min(mx,N);}else mx=min(61,N);fac[0]=1;for(int i=1;i<=N;i++)fac[i]=mul(fac[i-1],i);if(L>0){if(mn>mx){cout<<0<<"\n";return ( 0 - 0 );}K=mx;int qv=0;if(Q[N-1]==N){int rec=0,cm=0;for(int i=0;i<N;i++)if(Q[i]>cm)rec++,cm=Q[i];qv=(mn<=rec&&rec<=mx);}inv[N]=pw(fac[N],MOD-2);for(int i=N;i>=1;i--)inv[i-1]=mul(inv[i],i);PS=new int[(long long)(K+1)*N];calcPS();int cp=cnt_less(P),cq=cnt_less(Q);delete[] PS;int ans=sub(cq,cp);if(qv)ans=add(ans,1);cout<<ans<<"\n";}else{int ap=cnt_all(P),aq=cnt_all(Q);int all=sub(add(aq,1),ap);int np=cnt_N(P),nq=cnt_N(Q);int Nv=sub(add(nq,(Q[N-1]==N?1:0)),np);int ans=sub(all,Nv);if(mx>=1){K=mx;int qv=0;if(Q[N-1]==N){int rec=0,cm=0;for(int i=0;i<N;i++)if(Q[i]>cm)rec++,cm=Q[i];qv=(rec<=mx);}inv[N]=pw(fac[N],MOD-2);for(int i=N;i>=1;i--)inv[i-1]=mul(inv[i],i);PS=new int[(long long)(K+1)*N];calcPS();int sv=mn;mn=1;int cp=cnt_less(P),cq=cnt_less(Q);mn=sv;delete[] PS;int cv=sub(cq,cp);if(qv)cv=add(cv,1);ans=add(ans,cv);}cout<<ans<<"\n";}return ( 0 - 0 );
}