Bubble Sort Gym - 102222l题解

Bubble Sort 2018银川网络赛

题意： 给你一个1～n的序列，问你在k次冒泡后有多少排列能成为几乎排好序的序列。 几乎排好顺序的序列定义为 ： lcs >= n - 1;

题解： 此题是POJ3761的升级版本，也涉及到反序表的概念

反序表

反序表定义为： 令bi为位于i左边且大于i的元素的个数， 那么序列a1, a2, a3, a4...an 的反序表就为b1, b2, b3,b4...bn;

例如： 序列5 9 1 8 2 6 4 7 3
有反序表： 2 3 6 4 0 2 2 1 0

易得一些结论：
  1. 排列和反序表一一对应
  2. bi的取值为[0, n - i ]
  3. bi的取值与当前排列有关，和其他元素无关

题解

易证每次冒泡后，反序表中所有大于0的元素都至少会减一 那么目标可转换为求当k次冒泡后反序表全为零和lcs为n - 1的情况;

跑完k次冒泡后，后k个元素已经排好序，将他们各自的反序表可取值用加法原则相加，再用乘法原则，便能得到这k个元素能得到的序列数： 1 x 2 x 3 x 4 ,,,,, k, 也就是k!;

接着看剩下的n - k个元素，当k次冒泡后序列变成了顺序队列时，此时bi应该为 bi <= n - i + 1， 因为此时i <= n - k, 所以 bi 取值范围可大于等于k; 而k次排序只能保证减少k，所以剩下n - k个元素取值范围为k + 1, 即(k + 1) ^ (n - k)就是这种情况下的序列数量

下面讨论lcs为n - 1的情况， 我们先考虑当那个非lcs的数在序列最前面，那么后面n - k - 1个元素的可取值仍然为k + 1， 此时那个数，他的反序数只能比k + 1多， 当那个数为1,他的可取范围就为[k + 1, n - 1]， 依次类推，一直到[k + 1, k, + 1]， 以加法原则相加后再用乘法原则

\[ \sum_{i=1}^{n-k-1}{i}*(k+1)^{n-k-1} \]

当非lcs的数不在最前面，那么他肯定在中间废话, 在他前面的数就只能比他的反序数多，还只能一样，才能达成lcs， 那么取值范围就只能取最少的那个数。当取n - k - 1为非lcs数时n-k-1的反序数能取[0, k + 1]， 之前的数只能取k + 2, 以此类推，当这个数为1时会发现和之前考虑在最前面的重了，去掉即可

\[ \sum_{i=1}^{n-k-2}{i*({k+1})^i} \]

注意当k大于n时，直接算全排好就行

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
#include <cstdio>
#include <iostream>
#include <assert.h>

typedef long long ll;

ll mod;

ll fs(ll a, int b){
	ll ans = 1;
	while(b > 0){
		if(b & 1)ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

int main(){
	int T, q = 0;
	scanf("%d", &T);
	while(T--){
		int n, k;
		scanf("%d%d%lld", &n, &k, &mod);
		ll ans = fs(ll(k + 1), n - k);
		if(n >= k + 2)ans = (ans +  fs(ll(k + 1), n - k - 1) * ((n - k) * (n - k - 1) / 2) % mod) % mod;
		for(int i = 1; i < n - k - 1; i++)
			ans = (ans + 1ll * i * fs(ll(k + 1), i) % mod) % mod;
		for(int i = 1; i <= std::min(k, n); i++)
			ans = ans * i % mod;
		assert(ans >= 0);
		printf("Case #%d: %I64d\n", ++q, ans);
	}

	return 0;
}

Comments

2019-10-15
⬆︎TOP