Gioush OJ
⌕ 题目搜索注册登录
P1080 · OFFICIAL SOLUTION

P1080 旧词 官方题解

Gioush OJ · P1080 旧词

【部分分：测试点 1∼41\sim 41∼4】

  • 枚举下阕词节的全部排列，并依次与上阕词节配对。
  • 直接统计昂句与抑句的数量差，判断它是否等于 kk。
  • 时间复杂度为 O(n!n)\mathcal O(n!n)，空间复杂度为 O(n)\mathcal O(n)。

【部分分：测试点 5∼95\sim 95∼9】

  • 枚举排列的瓶颈仍然是方案数。把全部 2n2n 个音迹按强度从小到大排序，逐个决定它暂时等待，还是与更早出现的异类音迹配对。

  • 记 ui,viu_i,v_i 分别为前 ii 个音迹中上阕、下阕音迹的数量。

  • 定义 di,p,rd_{i,p,r} 为处理完前 ii 个音迹，已经完成 pp 组配对，其中恰有 rr 组昂句的方案数。

  • 初始时 d0,0,0=1d_{0,0,0}=1，其余不合法状态均为 00。

  • 当前音迹可以先不配对，因此始终有

di,p,r+=di−1,p,r.d_{i,p,r}\mathrel{+}=d_{i-1,p,r}.
  • 若第 ii 个音迹来自上阕，那么此前尚未配对的下阕音迹有 vi−1−pv_{i-1}-p 个。与其中任意一个配对都会形成昂句，因此
di,p+1,r+1+=(vi−1−p)di−1,p,r.d_{i,p+1,r+1}\mathrel{+}=(v_{i-1}-p)d_{i-1,p,r}.
  • 若第 ii 个音迹来自下阕，那么此前尚未配对的上阕音迹有 ui−1−pu_{i-1}-p 个。此时形成的是抑句，因此
di,p+1,r+=(ui−1−p)di−1,p,r.d_{i,p+1,r}\mathrel{+}=(u_{i-1}-p)d_{i-1,p,r}.
  • 若 n+kn+k 为偶数，令 r0=(n+k)/2r_0=(n+k)/2，最终答案为 d2n,n,r0d_{2n,n,r_0}；否则答案为 00。
  • 状态数为 O(n3)\mathcal O(n^3)，每个状态只有常数次转移。时间复杂度为 O(n3)\mathcal O(n^3)，滚动第一维后空间复杂度为 O(n2)\mathcal O(n^2)。

【部分分：测试点 10∼1410\sim 1410∼14】

  • 此时 k=nk=n，所有配对都必须是昂句。
  • 将两列音迹分别排序，记
li=∣{j∣bj<ai}∣.l_i=\left|\left\{j\mid b_j<a_i\right\}\right|.

按照 aia_i 从小到大的顺序配对。轮到 aia_i 时，前面已经用去 i−1i-1 个较弱下阕词节，因此还有 li−i+1l_i-i+1 种选择。

  • 因而答案为
∏i=1nmax⁡(0,li−i+1).\prod_{i=1}^{n}\max(0,l_i-i+1).
  • 排序后线性扫描即可，时间复杂度为 O(nlog⁡n)\mathcal O(n\log n)。

【部分分：测试点 15∼1915\sim 1915∼19】

  • 两类音迹在排序后交错出现。令 r=(n+k)/2r=(n+k)/2，若 n+kn+k 为奇数，答案仍为 00。
  • 先考虑
b1<a1<b2<a2<⋯<bn<an.b_1<a_1<b_2<a_2<\cdots<b_n<a_n.

把 aia_i 与 bpib_{p_i} 配对时，形成昂句当且仅当 pi≤ip_i\leq i。

  • 这与逆排列中的弱超越位置一一对应。令 em,je_{m,j} 为长度为 mm 的排列中恰有 jj 个弱超越位置的排列数，则
em,j=jem−1,j+(m−j+1)em−1,j−1,e1,1=1.e_{m,j}=j e_{m-1,j}+(m-j+1)e_{m-1,j-1}, \qquad e_{1,1}=1.
  • 在上一种交错顺序中，恰有 rr 组昂句的答案为 en,re_{n,r}。
  • 再考虑
a1<b1<a2<b2<⋯<an<bn.a_1<b_1<a_2<b_2<\cdots<a_n<b_n.

此时形成昂句当且仅当 pi<ip_i<i，也就是严格超越数。它与弱超越数的下标相差 11，答案为 en,r+1e_{n,r+1}。

  • 时间复杂度为 O(n2)\mathcal O(n^2)。使用滚动数组后，空间复杂度为 O(n)\mathcal O(n)。

【正解】

  • 设一组编排含有 rr 组昂句。由于昂句与抑句数量之和为 nn，需要满足
r−(n−r)=k.r-(n-r)=k.
  • 因而 r=(n+k)/2r=(n+k)/2。若 n+kn+k 为奇数，答案为 00。
  • 将两列音迹分别从小到大排序，并继续记
li=∣{j∣bj<ai}∣.l_i=\left|\left\{j\mid b_j<a_i\right\}\right|.
  • 定义 fi,jf_{i,j} 为只考虑前 ii 个上阕词节，选出其中 jj 个，并为它们钦定互不相同的较弱下阕词节的方案数。
  • 边界为 f0,0=1f_{0,0}=1，其余不合法状态为 00。不钦定 aia_i，或者把它与一个尚未使用的较弱下阕词节钦定为昂句，得到
fi,j=fi−1,j+(li−j+1)fi−1,j−1.f_{i,j}=f_{i-1,j}+(l_i-j+1)f_{i-1,j-1}.

  • 转移范围为 1≤i≤n1\leq i\leq n、0≤j≤min⁡(i,li)0\leq j\leq\min(i,l_i)，按照 ii 递增的顺序计算。

  • 钦定 jj 组昂句以后，其余 n−jn-j 组可以任意配对。记

gj=fn,j(n−j)!.g_j=f_{n,j}(n-j)!.
  • 这里 gjg_j 统计的是“完整编排与其中被钦定的 jj 组昂句”组成的二元组。
  • 记 hsh_s 为恰有 ss 组昂句的完整编排数。每种这样的编排可以从 ss 组昂句中选出 jj 组加以钦定，所以
gj=∑s=jn(sj)hs.g_j=\sum_{s=j}^{n}\binom{s}{j}h_s.
  • 第一种做法直接从 i=ni=n 开始向下计算。
  • gig_i 中还包含实际拥有更多昂句的编排。实际含有 s>is>i 组昂句的编排已经由 hsh_s 求出，并在 gig_i 中出现 (si)\binom{s}{i} 次。
  • 因此逐项扣除重复统计：
hi=gi−∑s=i+1n(si)hs.h_i=g_i-\sum_{s=i+1}^{n}\binom{s}{i}h_s.

  • 依次求到 hrh_r 即可。这一过程只是按照已知重复次数倒序扣除，不需要使用反演。

  • 第二种做法从

gj=∑s=jn(sj)hsg_j=\sum_{s=j}^{n}\binom{s}{j}h_s

出发，把它看作一个二项式变换。

  • 使用二项式反演，可以直接得到
hr=∑i=rn(−1)i−r(ir)gi.h_r=\sum_{i=r}^{n}(-1)^{i-r}\binom{i}{r}g_i.

  • 这个式子正好消去了“额外钦定昂句”带来的重复统计。

  • 把 gig_i 的表达式代入反演式，并交换求和顺序。对固定的 hsh_s，它的系数为

∑i=rs(−1)i−r(ir)(si).\sum_{i=r}^{s}(-1)^{i-r}\binom{i}{r}\binom{s}{i}.
  • 利用 (ir)(si)=(sr)(s−ri−r)\binom{i}{r}\binom{s}{i}=\binom{s}{r}\binom{s-r}{i-r}，这个系数等于
(sr)∑i=rs(−1)i−r(s−ri−r)=(sr)(1−1)s−r.\binom{s}{r}\sum_{i=r}^{s}(-1)^{i-r}\binom{s-r}{i-r} =\binom{s}{r}(1-1)^{s-r}.

它只有在 s=rs=r 时为 11，其余时候均为 00，所以反演式成立。

  • 两种做法共享同一个 fi,jf_{i,j}，区别只在于如何从 gjg_j 恢复恰好计数 hjh_j。
  • 预处理阶乘、逆阶乘与组合数后，转移和恢复答案都可以在 O(n2)\mathcal O(n^2) 时间内完成。
  • 空间复杂度为 O(n2)\mathcal O(n^2)。若滚动 ff 的第一维，可以降为 O(n)\mathcal O(n)。
  • 所有运算均对 998,244,353998{,}244{,}353 取模。

【参考代码】

/*Author:EhundateghDate:2026/8/31Name:verse.cppYou steal,I kill.*/#include <cstdio>#include <cstring>#include <algorithm>#define MAXN 2001using namespace std;const int Mod=998244353; int c,T,A[MAXN],B[MAXN],n,k,Larger[MAXN],Dp[MAXN][MAXN],R,F[MAXN];int Inv[MAXN]={0,1},Fact[MAXN]={1},Fact_Inv[MAXN]={1}; inline int Add(int a,int b){return (a+=b)>=Mod?a-Mod:a;}inline int Mul(int a,int b){return 1ll*a*b%Mod;}inline int Del(int a,int b){return (a-=b)>=0?a:a+Mod;} void Init(){    for(int i=1;i<=MAXN-1;i++) Fact[i]=Mul(Fact[i-1],i);    for(int i=2;i<=MAXN-1;i++) Inv[i]=Del(Mod,Mul(Inv[Mod%i],Mod/i));    for(int i=1;i<=MAXN-1;i++) Fact_Inv[i]=Mul(Inv[i],Fact_Inv[i-1]);} int C(int n,int m){return Mul(Mul(Fact[n],Fact_Inv[m]),Fact_Inv[n-m]);} void Solve(){    scanf("%d%d",&n,&k);    for(int i=1;i<=n;i++) scanf("%d",&A[i]);    for(int i=1;i<=n;i++) scanf("%d",&B[i]);    if((n+k)&1){puts("0");return;}    R=(n+k)/2;    sort(A+1,A+n+1);sort(B+1,B+n+1);    int Pointer=1;    for(int i=1;i<=n;i++){        while(Pointer<=n&&A[i]>B[Pointer]) Pointer++;        Larger[i]=Pointer-1;    }    memset(Dp,0,sizeof(Dp));memset(F,0,sizeof(F));    Dp[0][0]=1;    for(int i=1;i<=n;i++){        for(int j=0;j<=min(i,Larger[i]);j++){            Dp[i][j]=Dp[i-1][j];            if(j&&Larger[i]-j+1>0) Dp[i][j]=Add(Dp[i][j],Mul(Dp[i-1][j-1],Larger[i]-j+1));        }    }    for(int i=n;i>=R;i--){        F[i]=Mul(Dp[n][i],Fact[n-i]);        for(int j=n;j>i;j--) F[i]=Del(F[i],Mul(F[j],C(j,i)));    }    printf("%d\n",F[R]);    return;} int main(){    freopen("verse.in","r",stdin);    freopen("verse.out","w",stdout);    Init();scanf("%d%d",&c,&T);    while(T-->0) Solve();    return 0;}