P1080 旧词官方题解

Gioush OJ · 旧词 · 2026/09/07 00:00

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

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

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

枚举排列的瓶颈仍然是方案数。把全部 $2n$ 个音迹按强度从小到大排序，逐个决定它暂时等待，还是与更早出现的异类音迹配对。
记 $u_i,v_i$ 分别为前 $i$ 个音迹中上阕、下阕音迹的数量。
定义 $d_{i,p,r}$ 为处理完前 $i$ 个音迹，已经完成 $p$ 组配对，其中恰有 $r$ 组昂句的方案数。
初始时 $d_{0,0,0}=1$ ，其余不合法状态均为 $0$ 。
当前音迹可以先不配对，因此始终有

d_{i,p,r}\mathrel{+}=d_{i-1,p,r}.

若第 $i$ 个音迹来自上阕，那么此前尚未配对的下阕音迹有 $v_{i-1}-p$ 个。与其中任意一个配对都会形成昂句，因此

d_{i,p+1,r+1}\mathrel{+}=(v_{i-1}-p)d_{i-1,p,r}.

若第 $i$ 个音迹来自下阕，那么此前尚未配对的上阕音迹有 $u_{i-1}-p$ 个。此时形成的是抑句，因此

d_{i,p+1,r}\mathrel{+}=(u_{i-1}-p)d_{i-1,p,r}.

若 $n+k$ 为偶数，令 $r_0=(n+k)/2$ ，最终答案为 $d_{2n,n,r_0}$ ；否则答案为 $0$ 。
状态数为 $\mathcal O(n^3)$ ，每个状态只有常数次转移。时间复杂度为 $\mathcal O(n^3)$ ，滚动第一维后空间复杂度为 $\mathcal O(n^2)$ 。

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

此时 $k=n$ ，所有配对都必须是昂句。
将两列音迹分别排序，记

l_i=\left|\left\{j\mid b_j<a_i\right\}\right|.

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

因而答案为

\prod_{i=1}^{n}\max(0,l_i-i+1).

排序后线性扫描即可，时间复杂度为 $\mathcal O(n\log n)$ 。

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

两类音迹在排序后交错出现。令 $r=(n+k)/2$ ，若 $n+k$ 为奇数，答案仍为 $0$ 。
先考虑

b_1<a_1<b_2<a_2<\cdots<b_n<a_n.

把 $a_i$ 与 $b_{p_i}$ 配对时，形成昂句当且仅当 $p_i\leq i$ 。

这与逆排列中的弱超越位置一一对应。令 $e_{m,j}$ 为长度为 $m$ 的排列中恰有 $j$ 个弱超越位置的排列数，则

e_{m,j}=j e_{m-1,j}+(m-j+1)e_{m-1,j-1}, \qquad e_{1,1}=1.

在上一种交错顺序中，恰有 $r$ 组昂句的答案为 $e_{n,r}$ 。
再考虑

a_1<b_1<a_2<b_2<\cdots<a_n<b_n.

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

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

【正解】

设一组编排含有 $r$ 组昂句。由于昂句与抑句数量之和为 $n$ ，需要满足

r-(n-r)=k.

因而 $r=(n+k)/2$ 。若 $n+k$ 为奇数，答案为 $0$ 。
将两列音迹分别从小到大排序，并继续记

l_i=\left|\left\{j\mid b_j<a_i\right\}\right|.

定义 $f_{i,j}$ 为只考虑前 $i$ 个上阕词节，选出其中 $j$ 个，并为它们钦定互不相同的较弱下阕词节的方案数。
边界为 $f_{0,0}=1$ ，其余不合法状态为 $0$ 。不钦定 $a_i$ ，或者把它与一个尚未使用的较弱下阕词节钦定为昂句，得到

f_{i,j}=f_{i-1,j}+(l_i-j+1)f_{i-1,j-1}.

转移范围为 $1\leq i\leq n$ 、 $0\leq j\leq\min(i,l_i)$ ，按照 $i$ 递增的顺序计算。
钦定 $j$ 组昂句以后，其余 $n-j$ 组可以任意配对。记

g_j=f_{n,j}(n-j)!.

这里 $g_j$ 统计的是“完整编排与其中被钦定的 $j$ 组昂句”组成的二元组。
记 $h_s$ 为恰有 $s$ 组昂句的完整编排数。每种这样的编排可以从 $s$ 组昂句中选出 $j$ 组加以钦定，所以

g_j=\sum_{s=j}^{n}\binom{s}{j}h_s.

第一种做法直接从 $i=n$ 开始向下计算。
$g_i$ 中还包含实际拥有更多昂句的编排。实际含有 $s>i$ 组昂句的编排已经由 $h_s$ 求出，并在 $g_i$ 中出现 $\binom{s}{i}$ 次。
因此逐项扣除重复统计：

h_i=g_i-\sum_{s=i+1}^{n}\binom{s}{i}h_s.

依次求到 $h_r$ 即可。这一过程只是按照已知重复次数倒序扣除，不需要使用反演。
第二种做法从

g_j=\sum_{s=j}^{n}\binom{s}{j}h_s

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

使用二项式反演，可以直接得到

h_r=\sum_{i=r}^{n}(-1)^{i-r}\binom{i}{r}g_i.

这个式子正好消去了“额外钦定昂句”带来的重复统计。
把 $g_i$ 的表达式代入反演式，并交换求和顺序。对固定的 $h_s$ ，它的系数为

\sum_{i=r}^{s}(-1)^{i-r}\binom{i}{r}\binom{s}{i}.

利用 $\binom{i}{r}\binom{s}{i}=\binom{s}{r}\binom{s-r}{i-r}$ ，这个系数等于

\binom{s}{r}\sum_{i=r}^{s}(-1)^{i-r}\binom{s-r}{i-r} =\binom{s}{r}(1-1)^{s-r}.

它只有在 $s=r$ 时为 $1$ ，其余时候均为 $0$ ，所以反演式成立。

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

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/314Name:verse.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 200111using namespace std;12const int Mod=998244353;13 14int c,T,A[MAXN],B[MAXN],n,k,Larger[MAXN],Dp[MAXN][MAXN],R,F[MAXN];15int Inv[MAXN]={0,1},Fact[MAXN]={1},Fact_Inv[MAXN]={1};16 17inline int Add(int a,int b){return (a+=b)>=Mod?a-Mod:a;}18inline int Mul(int a,int b){return 1ll*a*b%Mod;}19inline int Del(int a,int b){return (a-=b)>=0?a:a+Mod;}20 21void Init(){22    for(int i=1;i<=MAXN-1;i++) Fact[i]=Mul(Fact[i-1],i);23    for(int i=2;i<=MAXN-1;i++) Inv[i]=Del(Mod,Mul(Inv[Mod%i],Mod/i));24    for(int i=1;i<=MAXN-1;i++) Fact_Inv[i]=Mul(Inv[i],Fact_Inv[i-1]);25}26 27int C(int n,int m){return Mul(Mul(Fact[n],Fact_Inv[m]),Fact_Inv[n-m]);}28 29void Solve(){30    scanf("%d%d",&n,&k);31    for(int i=1;i<=n;i++) scanf("%d",&A[i]);32    for(int i=1;i<=n;i++) scanf("%d",&B[i]);33    if((n+k)&1){puts("0");return;}34    R=(n+k)/2;35    sort(A+1,A+n+1);sort(B+1,B+n+1);36    int Pointer=1;37    for(int i=1;i<=n;i++){38        while(Pointer<=n&&A[i]>B[Pointer]) Pointer++;39        Larger[i]=Pointer-1;40    }41    memset(Dp,0,sizeof(Dp));memset(F,0,sizeof(F));42    Dp[0][0]=1;43    for(int i=1;i<=n;i++){44        for(int j=0;j<=min(i,Larger[i]);j++){45            Dp[i][j]=Dp[i-1][j];46            if(j&&Larger[i]-j+1>0) Dp[i][j]=Add(Dp[i][j],Mul(Dp[i-1][j-1],Larger[i]-j+1));47        }48    }49    for(int i=n;i>=R;i--){50        F[i]=Mul(Dp[n][i],Fact[n-i]);51        for(int j=n;j>i;j--) F[i]=Del(F[i],Mul(F[j],C(j,i)));52    }53    printf("%d\n",F[R]);54    return;55}56 57int main(){58    freopen("verse.in","r",stdin);59    freopen("verse.out","w",stdout);60    Init();scanf("%d%d",&c,&T);61    while(T-->0) Solve();62    return 0;63}