LOJ6077「2017 山东一轮集训 Day7」逆序对 （生成函数+多项式exp？朴素DP！）
题面
给定
n
,
k
n,k
n,k ，求长度为
n
n
n 逆序对个数为
k
k
k 的排列个数，对
1
e
9
+
7
\rm1e9+7
1e9+7 取模。
1
≤
n
,
k
≤
100
000
1\leq n,k\leq 100\,000
1≤n,k≤100000 。
题解
首先，不要看到逆序对就手忙脚乱，它其实是可控的。
令
d
i
d_i
di 为第
i
i
i 个数前面比它大的数的个数，满足条件
d
i
∈
[
0
,
i
)
d_i\in[0,i)
di∈[0,i) 。一个
d
d
d 序列，实际上只需要满足这个条件，他就能够成立，并且唯一对应一个排列。这个在POJ3761 Bubble Sort中证明过，可以通过
d
d
d 序列构造出排列来。
然后，就是个比较经典的问题：
n
n
n 个非负整数，各有上限，求总和为
k
k
k 的方案数。这题的特殊之处在于，每个数的上界依次是
0
0
0 到
n
−
1
n-1
n−1 。
先设
f
(
x
)
f(x)
f(x) 为这
n
n
n 个非负整数没有上限的情况下，总和为
x
x
x 的方案数。经验告诉我们，利用隔板法，可得
f
(
x
)
=
C
(
x
+
n
−
1
,
x
)
f(x)=C(x+n-1,x)
f(x)=C(x+n−1,x) 。
我们可以用生成函数来做，走起！
可以得到第
i
i
i 个数的生成函数为
1
+
x
+
x
2
+
.
.
.
+
x
i
−
1
=
(
∑
j
=
0
∞
x
j
)
−
(
∑
j
=
i
∞
x
j
)
=
1
−
x
i
x
−
1
1+x+x^2+…+x^{i-1}=(\sum_{j=0}^{\infty}x^j)-(\sum_{j=i}^{\infty}x^j)=\frac{1-x^i}{x-1}
1+x+x2+…+xi−1=(j=0∑∞xj)−(j=i∑∞xj)=x−11−xi
（我们用
[
[
x
i
]
]
F
(
x
)
[[x^i]]F(x)
[[xi]]F(x) 来表示函数
F
(
x
)
F(x)
F(x) 的
i
i
i 次项系数）于是答案可表示为
[
[
x
k
]
]
∏
i
=
1
n
1
−
x
i
x
−
1
=
[
[
x
k
]
]
(
(
1
x
−
1
)
n
∏
i
=
0
n
(
1
−
x
i
)
)
=
[
[
x
k
]
]
(
(
∑
i
=
0
∞
x
i
)
n
∏
i
=
0
n
(
1
−
x
i
)
)
=
∑
j
=
0
k
[
[
x
j
]
]
(
∑
i
=
0
∞
x
i
)
n
⋅
[
[
x
k
−
j
]
]
(
∏
i
=
0
n
(
1
−
x
i
)
)
[[x^k]]\prod_{i=1}^{n}\frac{1-x^i}{x-1}=[[x^k]]\Big((\frac{1}{x-1})^n\prod_{i=0}^{n}(1-x^i)\Big)\\ =[[x^k]]\Big((\sum_{i=0}^{\infty}x^i)^n\prod_{i=0}^n(1-x^i)\Big)\\ =\sum_{j=0}^{k}[[x^j]](\sum_{i=0}^{\infty}x^i)^n\cdot[[x^{k-j}]]\Big(\prod_{i=0}^n(1-x^i)\Big)
[[xk]]i=1∏nx−11−xi=[[xk]]((x−11)ni=0∏n(1−xi))=[[xk]]((i=0∑∞xi)ni=0∏n(1−xi))=j=0∑k[[xj]](i=0∑∞xi)n⋅[[xk−j]](i=0∏n(1−xi))
这个东西：
[
[
x
j
]
]
(
∑
i
=
0
∞
x
i
)
n
[[x^j]](\sum_{i=0}^{\infty}x^i)^n
[[xj]](∑i=0∞xi)n ，不就是无限制的
n
n
n 个自然数的情况吗？不就是
f
(
j
)
f(j)
f(j) ？
=
∑
j
=
0
k
f
(
j
)
⋅
[
[
x
k
−
j
]
]
(
∏
i
=
0
n
(
1
−
x
i
)
)
=\sum_{j=0}^{k}f(j)\cdot[[x^{k-j}]]\Big(\prod_{i=0}^n(1-x^i)\Big)
=j=0∑kf(j)⋅[[xk−j]](i=0∏n(1−xi))
接下来，我们要对这个函数
∏
i
=
0
n
(
1
−
x
i
)
\prod_{i=0}^n(1-x^i)
∏i=0n(1−xi) 开膛破肚了。
先取对数转化成加法：
exp
(
∑
i
=
0
n
ln
(
1
−
x
i
)
)
\exp\Big( \sum_{i=0}^n\ln(1-x^i) \Big)
exp(i=0∑nln(1−xi))
然后，我们手推二项式
ln
\ln
ln ，运用链式法则求导再求积分：
exp
(
∑
i
=
0
n
ln
(
1
−
x
i
)
)
=
exp
(
∑
i
=
0
n
∫
(
ln
′
(
1
−
x
i
)
⋅
(
1
−
x
i
)
′
)
d
x
)
=
exp
(
∑
i
=
0
n
∫
−
i
x
i
−
1
1
−
x
i
d
x
)
\exp\Big( \sum_{i=0}^n\ln(1-x^i) \Big)=\exp\Big( \sum_{i=0}^n\int(\ln'(1-x^i)\cdot(1-x^i)'){\rm dx} \Big)\\ =\exp\Big( \sum_{i=0}^n\int\frac{-ix^{i-1}}{1-x^i}{\rm dx} \Big)
exp(i=0∑nln(1−xi))=exp(i=0∑n∫(ln′(1−xi)⋅(1−xi)′)dx)=exp(i=0∑n∫1−xi−ixi−1dx)
再手推
g
(
x
)
=
1
−
x
i
g(x)=1-x^i
g(x)=1−xi 取模
x
k
+
1
x^{k+1}
xk+1 下的逆元。不难发现
(
1
−
x
i
)
(
1
+
x
i
+
x
2
i
+
x
3
i
+
.
.
.
)
=
1
−
x
i
+
x
i
−
x
2
i
+
x
2
i
−
.
.
.
≡
1
(1-x^i)(1+x^i+x^{2i}+x^{3i}+…)=1-x^i+x^i-x^{2i}+x^{2i}-…\equiv1
(1−xi)(1+xi+x2i+x3i+…)=1−xi+xi−x2i+x2i−…≡1 ，因此它的逆元是
h
(
x
)
=
1
+
x
i
+
x
2
i
+
x
3
i
+
.
.
.
h(x)=1+x^i+x^{2i}+x^{3i}+…
h(x)=1+xi+x2i+x3i+… 。代入进去：
exp
(
∑
i
=
0
n
∫
−
i
x
i
−
1
1
−
x
i
d
x
)
=
exp
(
∑
i
=
0
n
∫
−
i
x
i
−
1
(
∑
j
=
0
∞
x
i
j
)
d
x
)
=
exp
(
∑
i
=
0
n
∫
(
∑
j
=
1
∞
−
i
x
i
j
−
1
)
d
x
)
=
exp
(
∑
i
=
0
n
(
∑
j
=
1
∞
−
i
x
i
j
i
j
)
)
=
exp
(
∑
i
=
1
k
−
(
∑
j
∣
i
n
j
)
x
i
)
\exp\Big( \sum_{i=0}^n\int\frac{-ix^{i-1}}{1-x^i}{\rm dx} \Big)=\exp\Big( \sum_{i=0}^n\int-ix^{i-1}(\sum_{j=0}^{\infty}x^{ij}){\rm dx} \Big)\\ =\exp\Big( \sum_{i=0}^n\int(\sum_{j=1}^{\infty}-ix^{ij-1}){\rm dx} \Big)\\ =\exp\Big( \sum_{i=0}^n(\sum_{j=1}^{\infty}-i\frac{x^{ij}}{ij}) \Big)\\ =\exp\Big( \sum_{i=1}^{k} -(\sum_{j|i}^nj)x^i \Big)
exp(i=0∑n∫1−xi−ixi−1dx)=exp(i=0∑n∫−ixi−1(j=0∑∞xij)dx)=exp(i=0∑n∫(j=1∑∞−ixij−1)dx)=exp(i=0∑n(j=1∑∞−iijxij))=exp(i=1∑k−(j∣i∑nj)xi)
中间的
∑
j
∣
i
n
j
\sum_{j|i}^nj
∑j∣inj 其实就是
i
i
i 小于等于
n
n
n 的因数和，可以用埃筛预处理出来。然后再用多项式exp就可以求出这个多项式了，令该多项式的
i
i
i 次项系数为
G
[
i
]
G[i]
G[i] ，那么答案就是
∑
j
=
0
k
C
(
j
+
n
−
1
,
j
)
⋅
G
[
k
−
j
]
\sum_{j=0}^{k}C(j+n-1,j)\cdot G[k-j]
j=0∑kC(j+n−1,j)⋅G[k−j]
预处理阶乘求组合数就完了。时间复杂度
O
(
n
log
n
)
O(n\log n)
O(nlogn) 。还得写任意模数NTT之类。
但是多项式exp的常数有好几十，其实不优，很难跑过 1s。
我们其实可以用容斥，枚举超过上限的个数，答案转化过来，其实也是上面的一个式子：
∑
j
=
0
k
f
(
j
)
⋅
[
[
x
k
−
j
]
]
(
∏
i
=
0
n
(
1
−
x
i
)
)
\sum_{j=0}^{k}f(j)\cdot[[x^{k-j}]]\Big(\prod_{i=0}^n(1-x^i)\Big)
j=0∑kf(j)⋅[[xk−j]](i=0∏n(1−xi))
不熟悉生成函数的可能有点晕，但是熟知
D
P
\rm DP
DP 的我们应该可以意识到，右边的
[
[
x
k
−
j
]
]
(
∏
i
=
0
n
(
1
−
x
i
)
)
[[x^{k-j}]]\Big(\prod_{i=0}^n(1-x^i)\Big)
[[xk−j]](∏i=0n(1−xi)) 其实是个
0
/
1
0/1
0/1 背包问题！每个物品的大小依次是
1
1
1 到
n
n
n ，要么不取，要么取，取的话贡献的权值不是
1
1
1 而是
−
1
-1
−1，背包记录的是所有方案物品权值积的和。也可以说，绝对值是放物品方案数，符号是
−
1
-1
−1 的物品个数次方。
这个就很让人头疼。我们知道背包问题是根硬骨头，铁打的
O
(
n
m
)
O(nm)
O(nm) ，经常让人绝望。但是也不乏一些特殊情况的优化，比如用随机排序解决总和为
0
0
0 的背包最值问题（缩小背包大小），再比如这道题。这道题的特殊之处就在于每个物品的大小分别是
1
1
1 到
n
n
n 。
这样我们可以发现一个结论：物品个数不超过
k
\sqrt k
k
的级别！因为考虑最坏情况，只需要
1
1
1~
k
\sqrt k
k
放进去，总大小就足以达到
k
k
k 左右。
所以，设
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 为放
i
i
i 个数进去，总和为
j
j
j 的方案数，那么总状态数大约是
k
k
k\sqrt k
kk
，可以存得下。再借鉴LOJ#6089 小 Y 的背包计数问题的思路，我们可以进行
O
(
1
)
O(1)
O(1) 转移：
把已有的
i
i
i 个数每个加一，可得转移：
d
p
[
i
]
[
j
−
i
]
→
d
p
[
i
]
[
j
]
dp[i][j-i]\rightarrow dp[i][j]
dp[i][j−i]→dp[i][j] 。
把已有的数每个加一，再往里边放一个 1，可得转移
d
p
[
i
−
1
]
[
j
−
i
]
→
d
p
[
i
]
[
j
]
dp[i-1][j-i]\rightarrow dp[i][j]
dp[i−1][j−i]→dp[i][j] 。
上述两种转移算进来了不合法情况，即最大的数是一个
n
+
1
n+1
n+1 ，因此我们把这些情况去除掉。去掉最大的
n
+
1
n+1
n+1 后，方案数等于
d
p
[
i
−
1
]
[
j
−
n
−
1
]
dp[i-1][j-n-1]
dp[i−1][j−n−1] ，因此可得转移
(
−
d
p
[
i
−
1
]
[
j
−
n
−
1
]
)
→
d
p
[
i
]
[
j
]
(-dp[i-1][j-n-1])\rightarrow dp[i][j]
(−dp[i−1][j−n−1])→dp[i][j] 。
时间复杂度
O
(
k
k
)
O(k\sqrt k)
O(kk
) ，比多项式exp快得多。
CODE
动规做法
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define LL long long
#define DB double
#define ENDL putchar('\n')
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define SI(x) set<x>::iterator
#define BI bitset<63>
#define eps (1e-9)
#define SQ (450)
LL read() {
LL f=1,x=0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f*x;
}
void putpos(LL x) {
if(!x) return ;
putpos(x/10); putchar('0'+(x%10));
}
void putnum(LL x) {
if(!x) putchar('0');
else if(x < 0) putchar('-'),putpos(-x);
else putpos(x);
}
const int MOD = 1000000007;
int n,m,s,o,k;
int fac[MAXN<<2],inv[MAXN<<2],invf[MAXN<<2];
int C(int n,int m) {
if(m < 0 || m > n) return 0;
return fac[n] *1ll* invf[n-m] % MOD *1ll* invf[m] % MOD;
}
int dp[SQ][MAXN];
int dpp[MAXN];
int main() {
n = read();k = read();
int sq = 1;
while((sq+1)*1ll*(sq+2)/2ll <= k) sq ++;
fac[0]=fac[1]=inv[0]=inv[1]=invf[0]=invf[1]=1;
for(int i = 2;i <= 200000;i ++) {
fac[i] = fac[i-1]*1ll*i % MOD;
inv[i] = (MOD-inv[MOD%i]) *1ll* (MOD/i) % MOD;
invf[i] = invf[i-1] *1ll* inv[i] % MOD;
}
dp[0][0] = 1;
dpp[0] = 1;
for(int i = 1;i <= sq;i ++) {
for(int j = (i+1)*i/2;j <= k;j ++) {
dp[i][j] = (dp[i][j-i] + dp[i-1][j-i]) % MOD;
if(j > n) (dp[i][j] += MOD-dp[i-1][j-n-1]) %= MOD;
(dpp[j] += ((i&1) ? (MOD-1):1)*1ll*dp[i][j] % MOD) %= MOD;
}
}
int ans = 0;
for(int i = 0;i <= k;i ++) {
(ans += C(i+n-1,i) *1ll* dpp[k-i] % MOD) %= MOD;
}
printf("%d\n",ans);
return 0;
}手机扫一扫
移动阅读更方便
你可能感兴趣的文章