把所有数字放入双端队列后,结果大概是这样一个排列:
其中(P_1)是递减序列,(P_2)是递增序列。
我们以(1)所在的位置(k)分割最终的排列(A)。
其中前半部分,形象地讲是由两个递减序列交织在一起组成的。那两个递减序列分别是(P_1)的前缀和(P_2)的后缀,且至少有一个就是(P_1)((P_2))本身。那么,前半部分满足这个性质:
可以划分为两个可为空的递减子序列。
显然这个性质难以直接判定。考虑将其转化。对于其中编号为(i)的元素,设(j)是(i)后面的第一个与(A_i)属于不同子序列的元素位置。我们不妨分类讨论一发:
- (A_i > A_j),因为两个子序列递减,有(forall j in [i+1,k-1], \, A_i>A_j)
- (A_i < A_j),因为两个子序列递减,有(forall j in [1,i-1], \, A_i<A_j)
因此,我们得出:
长度为(n)的最终排列(A)的前半部分可以划分为两个可为空的递减子序列$implies ( ) forall i in [1,k-1]$,下列条件至少满足一个:
- (forall j in [i+1,k-1], \, A_i>A_j),记为条件1
- (forall j in [1,i-1], \, A_i<A_j),记为条件2
我们发现,逆命题也是成立的,因为最长不上升子序列的长度小于等于2。(导弹拦截可经典了)于是我们就获得了一个判断方法。
但还有一个问题,即从(1)到(n)的排列中任取出两个元素不重复的递减序列(D_1),(D_2),它们组成的序列(P),不一定可以作为(A)的前半部分。我们还要保证(D_1)的最后一个元素和(D_2)的最后一个元素中的较大值大于后半部分的所有元素。依然要对此进行转化。
那么,对于我们已知的一个(A)的前半部分,我们尝试将其划分且最大化两个子序列最后一个元素的较大值,设它的位置是(p)。显然(p)后面没有比(A_p)更大的元素,否则能得到更优解。通过简单分类讨论,我们发现所有不满足条件2的元素都大于后半部分的所有元素。因此我们可以直接修改条件2:
故我们得到了前半部分的判断方法。
后半部分的判断就简单多了。它是一个递减序列不断从前面或后面取出元素得到的,即每次取出的元素都是剩下的元素中最大(最小)的。容易得到且证明它合法的充要条件:
$ forall i in [k+1,n]$,下列条件至少满足一个:
- (forall j in [i+1,n], \, A_i > A_j)
- (forall j in [i+1,n], \, A_i < A_j)
我们终于简化了题意:
求有多少个长度为(n)的排列(A)满足:
- (A_k = 1)
- (forall i in [1,k)),(A_i)小于它前面的所有数或大于它后面的所有数。
- (forall i in (k,n]),(A_i)小于它后面的所有数或大于它后面的所有数。
剩下的就简单了。由递推式可知,后半部分的方案数就是(2^{n-k-1})。而对于前半部分,我们设dp状态(i,j)表示当前有(i)个元素,最小的满足条件2的元素是其中第(j)个(不存在则为(j+1)),最终答案就是
时间复杂度(O(n^2))。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2010, MOD = 1e9 + 7;
int dp[2][N],n,k,s,p,sum[N],ans,jc[N],inv[N];
typedef long long ll;
ll power(ll a,int b) {
ll res = 1;
while (b) {
if (b&1) (res *= a) %= MOD;
(a *= a) %= MOD;
b >>= 1;
}
return res;
}
ll comb(int a,int b) {
if (a < 0 || b < 0 || a < b) return 0;
return 1ll * jc[a] * inv[b] % MOD * inv[a-b] % MOD;
}
signed main() {
scanf("%lld%lld",&n,&k);
jc[0] = 1;
for (int i = 1 ; i <= n ; ++ i)
jc[i] = 1ll * jc[i-1] * i % MOD;
inv[n] = power(jc[n],MOD-2);
for (int i = n-1 ; i >= 0 ; -- i)
inv[i] = 1ll * inv[i+1] * (i+1) % MOD;
s = k-1;
p = 0;
sum[2] = 1;
sum[3] = -1;
for (int i = 1 ; i <= s ; ++ i) {
p ^= 1;
memset(dp[p],0,sizeof dp[p]);
for (int j = 1 ; j <= i+1 ; ++ j)
(sum[j] += sum[j-1]) %= MOD;
for (int j = 1 ; j <= i+1 ; ++ j)
(dp[p][j] += sum[j]) %= MOD, sum[j] = 0;
sum[i+2] = 0;
for (int j = 1 ; j <= i+1 ; ++ j) {
(sum[2] += dp[p][j]) %= MOD;
(sum[j+2] -= dp[p][j]) %= MOD;
}
}
for (int i = 1 ; i <= s + 1 ; ++ i) {
(ans += 1ll * comb(n-k+i-1,i-1) * dp[p][i] % MOD);
ans %= MOD;
}
if (k == 1) ans = 1;
if (n > k)
ans = 1ll * power(2,n-k-1) * ans % MOD;
ans = (ans + MOD) % MOD;
printf("%lld
",ans);
return 0;
}
小结:推导结论实在是一个困难的过程,积极的心态和清晰的思路是不可或缺的。