题意

LOJ6077 「2017 山东一轮集训 Day7」逆序对

给定 n,kn,k，求长度为 nn 的逆序对数恰为 kk 的排列个数，对 109+710^9+7 取模。
n,k≤105n,k\le 10^5。

生成函数做法

先考虑一个 O(nk)O(nk) 的朴素 dp。考虑按照位置一个一个插入数，假设当前插入第 ii 个数，根据插入的数与前面的数的大小，可以构成 [0,i−1][0,i-1] 个逆序对。

设 dpi,jdp_{i,j} 表示长度为 ii 的有 jj 个逆序对的排列数量：

dpi,j=∑max⁡(0,j−i+1)≤k≤jdpi−1,kdp_{i,j} = \sum_{\max(0,j-i+1)\le k\le j}dp_{i-1,k}

用前缀和就可以做到 O(nk)O(nk) 了。

我们考虑写出这个问题的生成函数，xpx^p 的系数表示逆序对个数为 pp 的排列个数。

一开始 F1=1F_1 = 1，之后每次能取的范围是 [0,i−1][0,i-1]，也就是 Fi=∑j=0ixjF_{i} = \sum_{j=0}^i x^j。
最后我们就是要求 [xk]∏i=1nFi[x^k]\prod_{i=1}^n F_i。

写成封闭形式：

∏i=1nFi=∏i=1n1−xi1−x=∏i=1n1−xi(1−x)n\begin{aligned} \prod_{i=1}^n F_i &=\prod_{i=1}^n\dfrac{1-x^i}{1-x}\\ &=\dfrac{\prod_{i=1}^n1-x^i}{(1-x)^n}\\ \end{aligned}

先考虑分母。可以证明 1(1−x)n=∑i=0∞(n+i−1n−1)xi\dfrac{1}{(1-x)^n} = \displaystyle\sum_{i=0}^{\infty} \dbinom{n+i-1}{n-1} x^i。

证明 1：
把 11−x\dfrac 1 {1-x} 展开为 ∑i=0∞xi\displaystyle\sum_{i=0}^\infty x^i。
所以 1(1−x)n=(∑i=0∞xi)n\dfrac{1}{(1-x)^n} = \left(\displaystyle\sum_{i=0}^\infty x^i\right)^n。

考察最后 xix_i 的系数，等价于选出 nn 个自然数和为 ii 的方案数，根据插板法可知答案为 (n+i−1i−1)\dbinom{n+i-1}{i-1}，故得证。

证明 2：
引理 1（广义牛顿二项式定理）：

(x+y)α=∑n=0∞xnyα−n(x+y)^{\alpha} = \sum_{n=0}^\infty x^n y^{\alpha-n}

其中 x,y,αx,y,\alpha 为实数，广义二项式系数定义为

(rn)={1n=0r(r−1)⋯(r−n+1)n!n>0\dbinom{r}{n} = \begin{cases} 1 & \text{} n=0 \\ \dfrac{r(r-1)\cdots (r-n+1)}{n!} & \text{} n>0 \end{cases}

其中 rr 为实数，nn 为自然数。

引理 2：

(−mn)=(−1)n(m+n−1m−1)\dbinom{-m}{n} = (-1)^n\dbinom{m+n-1}{m-1}

其中 nn 为自然数，mm 为实数。
证明：

(−mn)=(−m)(−m−1)⋯(−m−n+1)n!=(−1)n(m+n−1)(m−n)…mn!=(−1)n(m+n−1n)=(−1)n(m+n−1m−1)\begin{aligned} \dbinom{-m}{n} & = \dfrac{(-m)(-m-1)\cdots(-m-n+1)}{n!} \\ & = (-1)^n \dfrac{(m+n-1)(m-n)\ldots m}{n!}\\ & = (-1)^n \dbinom{m+n-1}{n}\\ & = (-1)^n \dbinom{m+n-1}{m-1} \end{aligned}

应用如上两个引理：

(1−x)−k=∑n=0∞(−kn)(−x)n=∑n=0∞(−1)n(k+n−1n)(−x)n=∑n=0∞(k+n−1n)xn\begin{aligned} (1-x)^{-k} &= \sum_{n=0}^{\infty}\dbinom{-k}{n}(-x)^n\\ &=\sum_{n=0}^{\infty}(-1)^n\dbinom{k+n-1}{n}(-x)^n\\ &=\sum_{n=0}^{\infty}\dbinom{k+n-1}{n}x^n\\ \end{aligned}

得到了一样结论。

由此，预处理出组合数，分母就可以在 O(n)O(n) 时间内计算了。

考虑分子：

∏i=1n(1−xi)\prod_{i=1}^n\left(1-x^i\right)

想要求出 xkx^k 的系数，问题就等价为有 nn 个物品，价值分别为 1,2,…,n1,2,\ldots,n，求出选奇数/偶数个物品，最终价值和为 kk 的方案数。

观察到选的物品数很少（是根号级别的）。
对于一个初始为 ∅\varnothing 的集合来说，我们考虑如下两种操作：

  • 操作 A\texttt A：只有集合非空才能执行，集合内所有的数加 11。
  • 操作 B\texttt B：集合内所有的数加 11，然后将 11 加入集合。

可以发现，任何一个递增序列都唯一对应一个操作序列，如 {1,4,5}\{1,4,5\} 对应 BBAAB\texttt{BBAAB}。

设 dpi,jdp_{i,j} 表示选了 ii 个数，和为 jj 的方案数，

dpi,j+i←dpi,j (操作 A)dpi+1,j+i+1←dpi,j (操作 B)\begin{aligned} dp_{i,j+i} &\leftarrow dp_{i,j}\text{ (操作 }\texttt{A}\text{)}\\ dp_{i+1,j+i+1} &\leftarrow dp_{i,j}\text{ (操作 }\texttt{B}\text{)}\\ \end{aligned}

这样就能在 O(kk)O(k\sqrt k) 复杂度内求出所有 dpdp 值（因为 i≤2k,j≤ki\le 2\sqrt k, j\le k），但是这样做是不对的，因为我们没有加入序列里的所有数都小于等于 nn 的限制。

为了解决这个问题，对于所有 dpi,j(j>n)dp_{i,j}(j>n)，都减去 dpi−1,j−n−1dp_{i-1,j-n-1}，这代表通过钦定最后一个数是 n+1n+1，减去了所有含 n+1n+1 的方案。

总结：

dpi,j=dpi,j−i+dpi−1,j−i−dpi−1,j−n−1dp_{i,j} = dp_{i,j-i} + dp_{i-1,j-i} - dp_{i-1,j-n-1}

（对于第二维 <0<0 的 dpdp 值忽略）

有了 dpdp 值，分子就可以改写为：

∏i=1n(1−xi)=∑i=0k∑j=0i(−1)j⋅dpj,i⋅xi\begin{aligned} \prod_{i=1}^n\left(1-x^i\right) &=\sum_{i=0}^{k}\sum_{j=0}^i(-1)^{j}\cdot dp_{j,i}\cdot x^i \end{aligned}

求出两个多项式的系数之后，直接 O(k)O(k) 求出最后乘积 xkx^k 项的系数就做完了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int MOD = 1e9+7;

const int N = 2e5+5;
int f[N],inv[N];
inline int C(int n,int r){return (r<0)?0:((ll)f[n]*inv[r]%MOD*inv[n-r]%MOD);}

int dp[2][N]; // 滚动数组
int coef[N]; // 分子部分 x^i 的系数

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    inv[0]=f[0]=inv[1]=f[1]=1;
    for(int i=2;i<N;i++)inv[i]=((ll)MOD-MOD/i)*inv[MOD%i]%MOD;
    for(int i=2;i<N;i++)inv[i]=(ll)inv[i-1]*inv[i]%MOD;
    for(int i=2;i<N;i++)f[i]=(ll)f[i-1]*i%MOD;

    int n,k; cin>>n>>k;
    dp[0][0] = 1; // 初始条件
    coef[0] = 1;
    for(int i=1,maxi=2*sqrt(k);i<=maxi;i++){
        for(int j=0;j<i;j++)dp[i%2][j]=0; // 清空滚动数组
        for(int j=i;j<=k;j++){
            dp[i%2][j] = (dp[(i-1)%2][j-i] + dp[i%2][j-i])%MOD;
            if(j>n)dp[i%2][j]=(dp[i%2][j]-dp[(i-1)%2][j-n-1]+MOD)%MOD;

            if(i%2==0)coef[j]=(coef[j]+dp[i%2][j])%MOD;
            else      coef[j]=(coef[j]-dp[i%2][j]+MOD)%MOD;
        }
    }
    int ans = 0;
    for(int i=0;i<=k;i++)ans = (ans + (ll)C(n+i-1,n-1)*coef[k-i])%MOD;
    cout << ans << '\n';

    return 0;
}

容斥做法

这个问题转化成有 nn 个变量 x1,x2,…,xnx_1,x_2,\ldots,x_n，xi∈[0,i−1]∩Zx_i\in [0,i-1]\cap \Z。
求 x1+x2+…+xn=kx_1+x_2+\ldots+x_n=k 的方案数。

考虑容斥，钦定 SS 内的变量不满足条件，即 ∀i∈S,xi≥i\forall i\in S,x_i\ge i，其他 xkx_k 不做要求，那么就先给每个 SS 内的变量分配对应的权值，剩下的再插板法就可以了。

写出容斥式子：

答案=∑S⊆{1,2,…,n}(−1)∣S∣(k+n−1−∑x∈Sxn−1)\text{答案}=\sum_{S\subseteq\{1,2,\ldots,n\}} (-1)^{|S|}\dbinom{k+n-1-\sum_{x\in S}x}{n-1}

直接枚举子集显然不现实，我们发现我们关心的只有子集的大小和子集内元素的和，这个就是有 nn 个物品，价值分别为 1,2,…,n1,2,\ldots,n，求出选奇数/偶数个物品，最终价值和为 kk 的方案数。

在上文已经叙述过了，最后代码也和之前的完全等价，式子也是相同的。