称满足 πi−1<πi 且 πi>πi+1 的 i 为「极大值」(1<i<n)。
整一个平凡又阴间的 DP……
设 f0/1,0/1(n,k) 分别表示 π1<π2 / π1>π2 且 πn−1<πn / πn−1>πn 的,有 k 个「极大值」的 n 阶排列。
容易观察得到 f0,0=f1,1 且 f0,1(n,k)=f1,0(n,k−1)。
然后开始阴间 DP 转移,对于 f0,0(n,k),考虑从 n−1 阶排列插入一个 n 得到 n 阶排列。
那么插入在「极大值」左右不会增加极大值,而其他位置都会。
则有 f0,0(n,k)=2kf0,0(n−1,k)+(n−2k−1)f0,0(n−1,k−1)+f0,0(n−1,k)+f0,1(n−1,k)+f1,0(n−1,k−1)
对于 f0,1(n,k),类似地有 f0,1(n,k)=2kf0,1(n−1,k)+(n−2k)f0,1(n−1,k−1)+f0,0(n−1,k−1)+f1,1(n−1,k−1)
进一步 {f0,1(n,k)=2kf0,1(n−1,k)+(n−2k)f0,1(n−1,k−1)+2f0,0(n−1,k−1)f0,0(n,k)=(2k+1)f0,0(n−1,kj)+(n−2k−1)f0,0(n−1,k−1)+2f0,1(n−1,k)
令 g(n,k)={f0,1(n,k2),k≡0(mod2)f0,0(n,k−12),k≡1(mod2)
于是有 g(n,k)=kg(n−1,k)+(n−k)g(n−1,k−2)+2g(n−1,k−1)
但是你发现这个阴间 DP 是没有前途的。
(但是所以我为什么要写呢?当然是为了膜拜卡老师!)
观察数据可以考虑求 g(n,n−1) 再倒推,因此考虑另一个 DP。
设 fn,gn 分别表示 π1<π2,πn−1>πn 和 π1<π2,πn−1<πn 且有 ⌊n−12⌋ 个「极大值」的排列个数。
DP 式比较显然,快进到 GF: F′=F2+1,G′=FG
这个微分方程比较好解,容易得到 F=tan,G=sec,于是可以得到 {g(n,n−1)} 的生成函数为 F+G=tan+sec,多项式求逆一下就好了。
考虑如何倒推,令 h(n,k)=g(n,n−k),则 DP 式可以写作 h(n,k)=(n−k)h(n−1,k−1)+kh(n−1,k+1)+2h(n−1,k)
考虑关于 k 改写这个式子 h(n,k+1)=1k[h(n+1,k)−(n−k+1)h(n,k−1)−2h(n,k)]
于是可以直接 O(n(n−2k)) 递推预处理答案。
总复杂度 O(nlogn+n(n−2k))。
比较卡常,我左转这里贴了一份 DIF / DIT,并左转这里学了个常数稍微小一点的求逆……
代码:
1 |
|