P1521 求逆序对【洛谷算法习题】
P1521 求逆序对
网页链接
P1521 求逆序对
题目描述
我们说( i , j ) (i,j)(i,j)是a 1 , a 2 , ⋯ , a N a_1,a_2,\cdots,a_Na1,a2,⋯,aN的一个逆序对，当且仅当i < j i<ji<j且a i > a j a_i>a_jai>aj。例如[ 2 , 4 , 1 , 3 , 5 ] [2,4,1,3,5][2,4,1,3,5]的逆序对有3 33个，分别为( 1 , 3 ) , ( 2 , 3 ) , ( 2 , 4 ) (1,3),(2, 3), (2, 4)(1,3),(2,3),(2,4)。现在已知N NN和K KK，求1 , 2 , 3 , ⋯ , N 1,2,3,\cdots,N1,2,3,⋯,N的所有特定排列，使得这些排列的逆序对的数量恰好为K KK。输出这些特定排列的数量。
例如N = 5 N=5N=5，K = 3 K=3K=3的时候，满足条件的排列有15 1515个，它们是：
- [ 1 , 2 , 5 , 4 , 3 ] [1, 2, 5, 4, 3][1,2,5,4,3]；
- [ 1 , 3 , 4 , 5 , 2 ] [1, 3, 4, 5, 2][1,3,4,5,2]；
- [ 1 , 3 , 5 , 2 , 4 ] [1, 3, 5, 2, 4][1,3,5,2,4]；
- [ 1 , 4 , 2 , 5 , 3 ] [1, 4, 2, 5, 3][1,4,2,5,3]；
- [ 1 , 4 , 3 , 2 , 5 ] [1, 4, 3, 2, 5][1,4,3,2,5]；
- [ 1 , 5 , 2 , 3 , 4 ] [1, 5, 2, 3, 4][1,5,2,3,4]；
- [ 2 , 1 , 4 , 5 , 3 ] [2, 1, 4, 5, 3][2,1,4,5,3]；
- [ 2 , 1 , 5 , 3 , 4 ] [2, 1, 5, 3, 4][2,1,5,3,4]；
- [ 2 , 3 , 1 , 5 , 4 ] [2, 3, 1, 5, 4][2,3,1,5,4]；
- [ 2 , 3 , 4 , 1 , 5 ] [2, 3, 4, 1, 5][2,3,4,1,5]；
- [ 2 , 4 , 1 , 3 , 5 ] [2, 4, 1, 3, 5][2,4,1,3,5]；
- [ 3 , 1 , 2 , 5 , 4 ] [3, 1, 2, 5, 4][3,1,2,5,4]；
- [ 3 , 1 , 4 , 2 , 5 ] [3, 1, 4, 2, 5][3,1,4,2,5]；
- [ 3 , 2 , 1 , 4 , 5 ] [3, 2, 1, 4, 5][3,2,1,4,5]；
- [ 4 , 1 , 2 , 3 , 5 ] [4, 1, 2, 3, 5][4,1,2,3,5]。
输入格式
输入共第一行，两个整数N NN和K KK。
输出格式
将1 ⋯ N 1\cdots N1⋯N的逆序对数量为K KK的特定排列的数量输出。为了避免高精度计算，请将结果对10000 1000010000取模后再输出。
输入输出样例 #1
输入 #1
5 3输出 #1
15说明/提示
数据范围及约定
对于全部数据，保证N ≤ 100 N \le 100N≤100，K ≤ N × ( N − 1 ) / 2 K \le N\times (N-1)/2K≤N×(N−1)/2。
解题思路
本题是插入法动态规划 + 滑动窗口优化的经典题型，核心是将逆序对的生成过程转化为逐个插入最大元素的累加贡献，并用前缀和与对称性优化转移效率。
1. 问题等价转化
- 逐步构造排列：考虑将数字1 ∼ N 1 \sim N1∼N按从小到大的顺序逐一插入到一个空序列中。由于第i ii个插入的数字i ii是当前最大的，无论它放在序列的哪个位置，都不会影响已存在数字之间的逆序关系。
- 逆序对贡献：将i ii插入到长度为i − 1 i-1i−1的序列中，有i ii个可能的插入位置。若插入在从右往左数第p pp个位置（p = 0 p=0p=0表示放在最右端，p = i − 1 p=i-1p=i−1表示放在最左端），则会新产生p pp个逆序对（i ii大于前面p pp个数字）。
- DP 定义：令
g[i][j]表示1 ∼ i 1 \sim i1∼i的所有排列中，逆序对总数恰好为j jj的排列个数。则转移方程为：
g [ i ] [ j ] = ∑ p = 0 min ( j , i − 1 ) g [ i − 1 ] [ j − p ] g[i][j] = \sum_{p=0}^{\min(j,\,i-1)} g[i-1][j-p]g[i][j]=p=0∑min(j,i−1)g[i−1][j−p]
初值g[0][0] = g[1][0] = 1。
2. 算法优化
直接按上述转移是O ( N 3 ) O(N^3)O(N3)的，不可接受。观察到转移是对前一行连续一段元素的求和，可以用滑动窗口优化到O ( N K ) O(NK)O(NK)：
- 递推式优化：对j ≥ 0 j \ge 0j≥0，有
g [ i ] [ j ] = g [ i ] [ j − 1 ] + g [ i − 1 ] [ j ] − ( j ≥ i ? g [ i − 1 ] [ j − i ] : 0 ) g[i][j] = g[i][j-1] + g[i-1][j] - (j \ge i \;?\; g[i-1][j-i] \;:\; 0)g[i][j]=g[i][j−1]+g[i−1][j]−(j≥i?g[i−1][j−i]:0)
这相当于用一个长度为i ii的窗口在g[i-1]上滑动求和。 - 对称性加速：对于长度为i ii的排列，逆序对的最大值d [ i ] = i ( i − 1 ) 2 d[i] = \frac{i(i-1)}{2}d[i]=2i(i−1)，且分布完全对称，即
g[i][j] = g[i][d[i]-j]。因此只需计算前一半（j ≤ d [ i ] / 2 j \le d[i]/2j≤d[i]/2）的值，后半部分直接复制，常数减半。
3. 算法步骤
- 初始化
d[1]=0，g[1][0]=1（代码里同时设了g[0][0]=1方便迭代）。 - 从小到大遍历i = 2 ∼ N i = 2 \sim Ni=2∼N：
- 计算最大逆序对数
d[i] = d[i-1] + i - 1。 - 对j jj从0 00到
d[i]/2，用滑动窗口公式计算g[i][j]，同时注意每一步对g[i-1][j]取模（模数10000 1000010000）。 - 对j jj从
d[i]/2 + 1到d[i]，通过对称性赋值g[i][j] = g[i][d[i]-j]。
- 计算最大逆序对数
- 最后输出
g[N][K] % 10000。
4. 复杂度分析
- 时间复杂度：O ( N × K ) O(N \times K)O(N×K)，N ≤ 100 N \le 100N≤100，K KK最大约4950 49504950，计算量约5 × 10 5 5 \times 10^55×105，非常充裕。
- 空间复杂度：O ( N × K ) O(N \times K)O(N×K)，存储 DP 表格。可以滚动数组优化至O ( K ) O(K)O(K)，但本题空间限制宽裕，未做也无妨。
总结
将逆序对构造问题转化为逐个插入最大元素的贡献累加，利用 DP 进行计数。滑动窗口将转移优化成常数时间，对称性减少一半计算量。整体思路清晰，代码实现简洁。
代码简要说明
全局变量与数组
d[i]：长度为i ii的排列的最大逆序对数。g[i][j]：1 ∼ i 1 \sim i1∼i的排列中逆序对数为j jj的方案数（全程对10000 1000010000取模）。
核心循环
- 外层
i从 2 到N NN，计算d[i]。 - 内层
j从 0 到d[i]/2：- 先对
g[i-1][j]取模。 - 按滑动窗口公式计算
g[i][j]（注意g[i][j-1]已在前一步算好，需保证计算顺序）。 - 若
j >= i，减去窗口左侧溢出的项g[i-1][j-i]。
- 先对
- 用对称性填充
j > d[i]/2的部分。
- 外层
输出：
cout << g[n][k] % 10000，确保取模。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,k,d[105],g[105][5000];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>k;g[0][0]=g[1][0]=1;for(ll i=2;i<=n;i++){d[i]=d[i-1]+i-1;for(ll j=0;j<=d[i];j++){g[i-1][j]%=10000;if(j<=d[i]/2){g[i][j]=g[i-1][j]+g[i][j-1];if(j>=i)g[i][j]-=g[i-1][j-i];}elseg[i][j]=g[i][d[i]-j];}}cout<<g[n][k]%10000<<endl;return0;}