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 ijij且a i a j a_ia_jaiaj。例如[ 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 N5N5K 3 K3K3的时候满足条件的排列有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输入 #15 3输出 #115说明/提示数据范围及约定对于全部数据保证N ≤ 100 N \le 100N≤100K ≤ 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 p0p0表示放在最右端p i − 1 pi-1pi−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_{p0}^{\min(j,\,i-1)} g[i-1][j-p]g[i][j]p0∑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]0g[1][0]1代码里同时设了g[0][0]1方便迭代。从小到大遍历i 2 ∼ N i 2 \sim Ni2∼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≤100K 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确保取模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,k,d[105],g[105][5000];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnk;g[0][0]g[1][0]1;for(ll i2;in;i){d[i]d[i-1]i-1;for(ll j0;jd[i];j){g[i-1][j]%10000;if(jd[i]/2){g[i][j]g[i-1][j]g[i][j-1];if(ji)g[i][j]-g[i-1][j-i];}elseg[i][j]g[i][d[i]-j];}}coutg[n][k]%10000endl;return0;}
