arc138e Decreasing Subsequence

题意

定义一个长度为 nn 的序列 aa 为好序列，当且仅当满足以下两个条件。

  • 0≤ai≤i(1≤i≤n)0\leq a_i\leq i(1\leq i\leq n)

  • 对于每个 v∈[1,n]v\in[1,n]，序列 aa 中最多只有一次 vv 的出现。

对于每个好序列，统计长度为 kk 的严格递减子序列的数量并求和，且子序列中不能出现 00。

n,k≤5000n,k\leq5000

做法

我们先来转化一下好序列的形式。考虑如下这个转换。

在 ii 时获得一个写着 ii 的球，然后从你拥有的球中选择一个放在 aia_i 或者不选。

考虑一组严格递减子序列的下标 i1,i2,...,iki_1,i_2,...,i_k。

容易发现，所有的 aija_{i_j} 都小于等于 i1i_1。

这个好序列也可以理解为，把 i1i_1 前面的 kk 个球留下来放到 i1i_1 后面的 kk 个位置。

于是考虑对答案计数的时候枚举第一个位置即 i1i_1。

然后将整个序列以 i1i_1 为分界点分别 dp。

记 f(i,j)f(i,j) 表示前 ii 个位置已经填好，剩下 jj 个球没有被填，且这 jj 个球一定会在后面被用到。

一定会被用到的限制在后面合并的时候，左边的总个数一定等于右边的总个数，不用枚举再优化了。

转移的时候分类讨论第 ii 个位置是填 00 还是选数，这个位置的球是空闲还是扔掉。

那么写出转移式。

f(i,j)←f(i−1,j−1)f(i,j)←f(i−1,j)f(i,j)←f(i−1,j)×(j+1)f(i,j)←f(i−1,j+1)×(j+1)f(i,j)\leftarrow f(i-1,j-1)\\ f(i,j)\leftarrow f(i-1,j)\\ f(i,j)\leftarrow f(i-1,j)\times(j+1)\\ f(i,j)\leftarrow f(i-1,j+1)\times(j+1)

对于后面记 g(i,j)g(i,j) 表示 [i,n][i,n] 已经填好，用了前面的 jj 个球。

写出转移式后发现竟然和 ff 的转移式一模一样。

所以有 g(i+1,j)=f(n−i,j)g(i+1,j)=f(n-i,j)。

然后合并的时候，对于枚举出来的 i1i_1 也要讨论。

下面用 ii 代替 i1i_1 方便讨论。

统计答案的时候，枚举共有 jj 个左边的球（包括 ii）放到右边去。从中选 kk 个作为递减子序列。

共三种情况。

  1. ii 的球被用在了递减子序列中，那么一定是就放在 ii。对答案的贡献为(j−1k−1)×(j−1k−1)×(j−k)!×f(i−1,j−1)×g(i+1,j−1)\binom {j-1} {k-1}\times\binom {j-1} {k-1}\times (j-k)!\times f(i-1,j-1)\times g(i+1,j-1)。
  2. ii 的球被用在了非递减子序列中，后面有 j−1j-1 个位置可以随便选择，贡献为(j−1k)×(j−2k−1)×(j−k−1)!×f(i−1,j−1)×g(i+1,j−1)×(j−1)\binom {j-1} {k}\times\binom {j-2} {k-1}\times (j-k-1)!\times f(i-1,j-1)\times g(i+1,j-1)\times(j-1)。
  3. ii 的球被扔掉了，贡献为 (jk)×(j−1k−1)×(j−k)!×f(i−1,j)×g(i+1,j−1)\binom {j} {k}\times\binom {j-1} {k-1}\times (j-k)!\times f(i-1,j)\times g(i+1,j-1)。

前面两种情况都是用到了 ii 放到后面，所以前面要选 j−1j-1 个，第三种情况不用 ii 了，前面选 jj 个。

而后面因为 ii 是必选的，所以都还要选 j−1j-1 个。

做完了。

时间复杂度：O(n2)O(n^2)

空间复杂度：O(n2)O(n^2)

参考代码

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
49
#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=5010,mod=1e9+7;
int n,k;
int C[N][N],f[N][N];
int fac[N];
int ans=0;
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>k;
	forn(i,0,5000)C[i][0]=1;
	forn(i,1,5000)forn(j,1,i)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	fac[0]=1;
	forn(i,1,5000)fac[i]=fac[i-1]*i%mod;
	f[0][0]=1; 
	forn(i,1,n){
		forn(j,0,n){
			if(j)f[i][j]+=f[i-1][j-1]%mod;
			f[i][j]+=f[i-1][j]*(j+2)%mod;
			f[i][j]+=f[i-1][j+1]*(j+1)%mod;
			f[i][j]%=mod;
		}
	}
	forn(i,1,n){
		forn(j,k,n){
			int coef=C[j-1][k-1]*C[j-1][k-1]%mod*fac[j-k]%mod;
			ans+=f[i-1][j-1]*f[n-i][j-1]%mod*coef%mod;ans%=mod;
			coef=C[j][k]*C[j-1][k-1]%mod*fac[j-k]%mod;
			ans+=f[i-1][j]*f[n-i][j-1]%mod*coef%mod;ans%=mod;
			coef=C[j-1][k]*C[j-2][k-1]%mod*fac[j-k-1]%mod;
			ans+=f[i-1][j-1]*f[n-i][j-1]%mod*(j-1)%mod*coef%mod;ans%=mod;
		}
	}
	cout<<ans<<"\n";
	return 0;
}