Reincarnation

正因为梦易碎，才格外美好。

P8859 冒泡排序

发表于 更新于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

总之啊，和“冒泡排序”沾边的题都是毒瘤。

首先，这种分 的问题就真的恶心，非要把两道题揉成一道题来考。纯属恶心人。

我们于是就按照他挖的坑来寄做。

Type I

这是一个计数题，所以考虑 或者是组合数，或者两个都考虑。用 表示插入到了第 个数，需要操作的有 个才能使其成为升序排序数列的序列个数。递推公式是：

事实上，这是第一类 数，答案 。

Type II

对于环上操作，结论好像和什么单调栈长度有关（ 爷说的），不太清楚。然后记录 状态，为 表示 个数，当前单调栈最大长度为 的序列计数。

然后组合数 记忆化搜索乱搞，贺 爷的代码。

AC Code
 
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// ----- Eternally question-----
// Problem: P8859 冒泡排序
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8859
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2022-11-22 15:29:42
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef long double ld;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e2+10;
const int Mod=1e9+7;
int N,K,Type;
inline void add(int &a,int b){ if((a+=b)>=Mod) a-=Mod; }
namespace SolveSeq
{
	int Dp[MAXN][MAXN];
	inline bool main()
	{
		Dp[0][0]=1;
		for(int i=0;i<N;++i)
			for(int j=0;j<=i;++j)
				add(Dp[i+1][j+1],Dp[i][j]),add(Dp[i+1][j],1ll*Dp[i][j]*i%Mod);
		write(Dp[N][N-K]);
		return 0;
	}
};
namespace SolveCircle
{
	int C[MAXN][MAXN],Dp[MAXN][MAXN];
	inline void initC()
	{
		for(int i=C[0][0]=1;i<MAXN;++i)
			for(int j=C[i][0]=1;j<=i;++j)
				add(C[i][j]=C[i-1][j],C[i-1][j-1]);
	}
	int solve(int n,int k)
	{
		if(n==0) return 1;
		if(k<=0) return 0;
		if(Dp[n][k]) return Dp[n][k];
		int &res=Dp[n][k];
		for(int mid=1;mid<=n;++mid)
			add(res,1ll*C[n-1][mid-1]*solve(mid-1,k)%Mod*solve(n-mid,k-1)%Mod);
		return res;
	}
	inline bool main()
	{
		initC();
		int res=solve(N-1,N-K-1);
		add(res,Mod-solve(N-1,N-K-2));
		write(res);
		return 0;
	}
};
int main()
{
	// freopen("sort.in","r",stdin);
	// freopen("sort.out","w",stdout);
    read(N,K,Type);
	if(Type==1) return SolveSeq::main();
	else return SolveCircle::main();
	return 0;
}
/*

*/
相关文章