Description
https://www.luogu.com.cn/problem/P8859
Solution
妙妙题。
首先考察第一问。手玩一下发现最优是每次从 $1\sim n$ 选，一个数不操作当且仅当这个数是前缀最大值。所以只需要统计前缀最大值的个数为 $n-k$ 即可。
也可以当成前缀最小值的个数。记 $f_{i,j}$ 表示选到第 $i$ 个数，前缀最大值的个数为 $j$ 的方案数。则有贡献当且仅当放在第一位，则有 $f_{i,j}=f_{i-1,j}\times(i-1)+f_{i-1,j-1}$。事实上这是第一类斯特林数。复杂度 $O(n^2)$。
接下来考察第二问。先考虑怎么计算 $f(A)$ 。事实上因为有一个数肯定不操作，所以我们可以钦定这个数然后断环为链。$f(A)$ 就是所有情况下的最小值。
考虑转化到第一问，我们把每个数连向环上第一个大于它的，图的最长路就是 $n-f(A)$。$n$ 是没有出边的，所以钦定 $a_n=n$，这样就成了一条链。
容易发现图是一棵根为 $n$ 的有根树，满足父亲大于儿子，最长路就是其最大深度，且和每个 $a_n=n$ 的排列构成双射。题目转化为我们只需要统计满足父亲大于儿子的且深度为 $n-k$ 的方案数。
记 $f_{i,j}$ 表示选了 $i$ 个点，深度为 $j$ 的树的方案树。转移有 $f_{i+j,\max(d1,d2+1)}\gets f_{i,d1}\times f_{j,d2}\times C$，为了保证不重不漏，钦定每次合并过来的子树大小递减。所以系数 $C=\dbinom{i+j-2}{i-1}$。前缀和优化一下，复杂度 $O(n^3)$。
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define maxn 505
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
ll power(ll x,int y=mod-2) {
ll sum=1;x%=mod;
while (y) {
if (y&1) sum=sum*x%mod;
x=x*x%mod;y>>=1;
}
return sum;
}
int n,k,op;
int c[maxn][maxn],f[maxn][maxn],g[maxn][maxn];
void add(int &x,int y) {x=(x+y)%mod;}
signed main(void){
freopen("1.in","r",stdin);
int i,j;
read(n);read(k);read(op);
for (i=0;i<=n;i++) {
c[i][0]=1;
for (j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
if (op==1) {
f[1][1]=1;
for (i=2;i<=n;i++)
for (j=1;j<=n;j++)
add(f[i][j],f[i-1][j]*(i-1)+f[i-1][j-1]);
printf("%lld\n",f[n][n-k]);
return 0;
}
int K=k;
f[1][1]=1;
for (i=1;i<=n;i++) g[1][i]=1;
for (i=2;i<=n;i++) {
for (j=2;j<=n;j++) {
if (j<=i) {
for (k=1;k<i;k++)
add(f[i][j],(f[k][j]*g[i-k][j-1]+g[k][j-1]*f[i-k][j-1])%mod*c[i-2][k-1]);
}
add(g[i][j],g[i][j-1]+f[i][j]);
}
}
printf("%lld\n",f[n][n-K]);
return 0;
}
|