【题解】HackerRank - Sherlock's Array Merging Algorithm

题目

https://www.hackerrank.com/challenges/sherlocks-array-merging-algorithm/problem

题解

  • 每一列的数在原数列中是连续且单调增的
  • 每一列数的个数是单调减的

如果原数列是单调递增的,可以使用如下代码。其中 dp[i][j] 表示前 i 个数分成若干组且最后一组的大小为 j 的总方案数。

1
2
3
4
5
FOR(i, 1, n + 1) {
dp[i][i] = 1;
FOR(j, 1, i + 1) {
FOR(k, j, i + 1) {
dp[i][j] += dp[i - j][k] * A(k, j); // A 是排列数

  • 需要预处理阶乘和阶乘的逆元
  • 看起来复杂度是\(O(n^3)\)的,但是其实是\(O(n^3/6)\),所以竟然没有超时?

完整代码

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
#include <bits/stdc++.h>
#define FOR(i, x, y) for (remove_const<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (remove_const<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
using namespace std;
typedef long long LL;
const int maxn = 1200 + 5;
const int MOD = 1E9 + 7;
LL dp[maxn][maxn], n, a[maxn], l[maxn];
LL invf[maxn], factor[maxn];

LL quick_inverse(LL n, LL p) {
LL ret = 1;
LL exponent = p - 2;
for (LL i = exponent; i; i >>= 1, n = n * n % p) {
if (i & 1) {
ret = ret * n % p;
}
}
return ret;
}

void get_factorial_inverse(LL n, LL p) {
factor[0] = 1;
for (LL i = 1; i <= n; ++i) {
factor[i] = i * factor[i - 1] % p;
}
invf[n] = quick_inverse(factor[n], p);
for (LL i = n-1; i >= 0; --i) {
invf[i] = invf[i + 1] * (i + 1) % p;
}
}

inline LL A(LL n, LL m) { return factor[n] * invf[n - m] % MOD; }

int main() {
cin >> n;
get_factorial_inverse(n, MOD);
FOR(i, 0, n) scanf("%lld", &a[i]);
l[0] = 1;
FOR(i, 1, n) if (a[i] >= a[i - 1]) l[i] = l[i - 1] + 1; else l[i] = 1;
FOR(i, 1, n + 1) {
FOR(j, 1, l[i - 1] + 1) {
if (i == l[i - 1]) dp[i][i] = 1;
FOR(k, j, i - j + 1)
dp[i][j] = (dp[i][j] + dp[i - j][k] * A(k, j)) % MOD;
}
}
LL ans = 0;
FOR(i, 1, l[n - 1] + 1) ans += dp[n][i];
cout << ans % MOD << endl;
}