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

Posted on Edited on In Disqus:

题目

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;
}