「SDTT 2017」逆序对

Problem

Description

给定 n,k ,请求出长度为 n 的逆序对数恰好为 k 的排列的个数。

答案对 10^{9}+7 取模。

Constraints

1\le n\le 10^{5},1\le k\le\min\left(\binom{n}{2},10^{5}\right)

Solution

Analysis

考虑从小到大加数,容易发现在加进数 i 后逆序对数 k 的改变值 \Delta k\in[0, i - 1]
故其 OGF 为:

A(x)= \prod_{i = 1}^{n} \sum_{j = 0}^{i - 1} x^{j} = \prod_{i = 1}^{n} \frac{1 - x^{i}}{1 - x} = \frac{ \prod_{i = 1}^{n} \left(1-x^{i}\right)}{\left(1-x\right)^{n}}

设:

f(x) = \prod_{i = 1}^{n}\left(1-x^{i}\right)

g(x) = \frac{1}{\left(1-x\right)^{n}} = \left(\sum_{i = 0}^{+\infty}x^{i}\right)^{n}

则:

A(x) = (f \cdot g)(x)


考虑 f(x) k 次项系数 [x^{k}] f(x) ,记其为 f_{k}

F(r, k) 为满足

\prod_{i = 1}^{r}x^{a_{i}}=x^{k},\forall i,j\in[1, r],i\ne j:a_{i}\in[1, n],a_{i}\ne a_{j}

亦即

\sum_{i = 1}^{r}a_{i}=k,\forall i,j\in[1, r],i\ne j:a_{i}\in[1, n],a_{i}\ne a_{j}

的长度为 r 的数列 \{a_{n}\} 的个数。
则对于每个 r F(r, k) f(x) k 次项系数 f_{k} 的贡献为 (-1)^{r}F(r, k) ,其中 (-1)^{r} f(x) 表达式中 r x^{a_{i}} 的系数之积。
f(x) k 次项系数 f_{k} 为:

f_{k}=\sum_{r = 0}^{n}\left((-1)^{r}F(r, k)\right)


考虑 g(x) k 次项系数 [x^{k}]g(x) ,记其为 g_{k}
易知其为从 \left[0,+\infty\right) 中选取 n 个可重复的数使其和为 k 的方案数。
经典组合数问题。

g_{k}=\binom{k+n-1}{n-1}


故 OGF A(x)=(f \cdot g)(x) k 次项系数为:

[x^{k}]A(x)=\sum_{i = 0}^{k}\sum_{j = 0}^{k}[i + j = k] f_{i}g_{j}=\sum_{i = 0}^{k}f_{i}g_{k-i}=\sum_{i = 0}^{k}\binom{k-i+n-1}{n-1}\sum_{r = 0}^{n}(-1)^{r}F(r, k)

答案为:

\sum_{i = 0}^{k}\binom{k-i+n-1}{n-1}\sum_{r = 0}^{n}(-1)^{r}F(r, k)

组合数可以 O(n + k) 处理得到。考虑如何计算 F(r, k)

可以发现每个数列 \{a_{n}\} 都可以用如下两种操作从初始数列 \{a_{n}\}=\left\{1\right\} 转化而来:

  1. \{a_{n}\}\rightarrow\left\{a_{n}+1\right\}
  2. \left\{a_{1},a_{2},...,a_{n}\right\}\rightarrow\left\{a_{1}+1,a_{2}+1,...,a_{n}+1,1\right\}

那么每个 F(r, k) 都是从 F(r-1,k-r) F(r,k-r) 转移而来的。
又考虑到在这样操作的过程中可能会有 \exists i:a_{i}=n+1 的不合法方案,考虑在 F(r, k) 中减去其贡献。

因为 \exists i:a_{i}=n+1 的不合法方案可以看作从方案 F(r-1,k-(n + 1)) 加上一个数 (n + 1) 而来,所以不合法的方案数即为 F(r-1,k-(n + 1)) ,将其从 F(r, k) 中减去即可。
F(r, k) 的递推式为:

F(r, k)=[r\le k]\left(F(r-1,k-r)+F(r,k-r)\right)-[n+1\le k]F(r-1,k-(n + 1))

带上容斥系数之后为

F(r, k)=[r\le k]\left(F(r-1,k-r)-F(r,k-r)\right)+[n+1\le k]F(r-1,k-(n + 1))

容易发现在 r \sqrt{k} 级别时 F(r, k) 趋近于 0

\sum_{r = 1}^{\sqrt{k}}= \frac{\sqrt{k}\left(\sqrt{k}+1\right)}{2}\approx k

故在答案式中对于每个 k 有贡献的 r 只有 \sqrt{k} 个(确切地说,是 \left(\sqrt{2k+ \frac{1}{4}}- \frac{1}{2}\right) 个)。

时间复杂度 O\left(k\sqrt{k}\right)

Code

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
40
41
42
43
44
45
46
47
48
#include<cstdio>

constexpr int p=1000000007;
constexpr int Maxn=200000;
constexpr int Maxm=450;

inline void inc(int&x,const int&y)
{x+=y;(x>=p)&&(x-=p);}
inline void dec(int&x,const int&y)
{x-=y;(x<0)&&(x+=p);}
inline int fpow(const int&x,int n){
int Ans=1;
for(int b=x;n;n>>=1,b=1LL*b*b%p)
if(n&1)Ans=1LL*Ans*b%p;
return Ans;
}

int Fac[Maxn+1];
int invFac[Maxn+1];
int F[Maxm][Maxn+1];

inline int C(const int&n,const int&k)
{return 1LL*Fac[n]*invFac[n-k]%p*invFac[k]%p;}

int main(){
int n,k;scanf(" %d %d",&n,&k);

Fac[0]=invFac[0]=1;
for(int i=1,_=n+k;i<=_;++i)
Fac[i]=1LL*Fac[i-1]*i%p;
invFac[n+k]=fpow(Fac[n+k],p-2);
for(int i=n+k-1;i;--i)
invFac[i]=1LL*invFac[i+1]*(i+1)%p;

F[0][0]=1;
for(int i=1;i<Maxm;++i)
for(int j=0;j<=k;++j){
if(i<=j)inc(F[i][j],F[i][j-i]),dec(F[i][j],F[i-1][j-i]);
if(n+1<=j)inc(F[i][j],F[i-1][j-n-1]);
}

int Ans=0;
for(int i=0,tmp=0;i<=k;inc(Ans,1LL*tmp*C(n+k-i-1,n-1)%p),tmp=0,++i)
for(int j=0;j<Maxm;++j)
inc(tmp,F[j][i]);

return printf("%d",Ans),0;
}