【题解】EOJ - 棋盘上的車 (bzoj 2616 - SPOJ PERIODNI)

Posted on Edited on In Disqus:

题目

http://acm.ecnu.edu.cn/problem/3438/

题意

给定一个由 n 条高度不等的列组成的棋盘，其中所有列的底边位于同一水平线上。求放置 k 个互不攻击的車的方案总数。（車能互相攻击当且仅当能通过棋盘上连续的一行或一列格子直接连在一起）

题解

  • 观察到从最下面一行开始往上，行断开后不可能重新接在一起，所以从断开处横向切开很可能可以分解为两个子问题。当然也可以把它看做是一棵树，树上的每一个结点有高和宽，只有有公共边的情形下两个结点才会相连。

  • 但是如果不建树则可以看成区间 dp。

  • \(dp[x][k]\) 表示底为 \([l, r]\) 子树（子树根节点编号为 \(x\)）上恰好放置 \(k\) 个的方案数。

  • 这棵树为二叉树，也就是一个区间从区间最小值那里分割出两个结点。但是如果区间内有多个最小值，那么任取一个即可，省去了很多麻烦。（至于为什么是对的，因为计算中允许了高度为 0 的结点。）

  • 设当前结点为 x，两个子结点分别为 a, b，当前结点的高度和宽度分别为 \(height\) 和 \(length\)。

  • 枚举当前结点以及 a 和 b 放置的車的数目得到状态转移方程

    \[dp[x][k]=\displaystyle \sum_{i=0}^{k} {length-k+i \choose i} {height \choose i} i!\sum_{j=0}^{k-i}dp[a][j] \times dp[b][k-i-j]\]

  • 可惜这样会超时，所以预处理后面一个求和符号中的值，记为\(g[k-i]​\)，那么有\(g[k]=\sum_{i=0}^k dp[a][i] \times dp[b][k-i]​\)，可以在 \(O(length^2)​\) 内预处理。

  • 此时状态转移方程变为\(dp[x][k]=\displaystyle \sum_{i=0}^{k} {length-k+i \choose i} {height \choose i} i! \times g[k-i]\)，也可以在 \(O(length^2)\) 内处理出来（还要枚举 k）。当然这道题还需要预处理阶乘以及阶乘的逆元使得组合数计算\(O(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
68
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const LL maxn = 5E2 + 100, MOD = 1E9 + 7, M = 1E6 + 10;
LL h[maxn], f[maxn][maxn], g[maxn];

inline void up(LL& a, LL b) { (a += b) %= MOD; }

LL pown(LL x, LL n, LL MOD) {
    LL ret = MOD != 1;
    for (x %= MOD; n; n >>= 1, x = x * x % MOD)
        if (n & 1) ret = ret * x % MOD;
    return ret;
}

LL invf[M], fac[M];
void fac_inv_init(LL n, LL p) {
    fac[0] = 1;
    FOR (i, 1, n)
        fac[i] = i * fac[i - 1] % p;
    invf[n - 1] = pown(fac[n - 1], p - 2, p);
    FORD (i, n - 2, -1)
        invf[i] = invf[i + 1] * (i + 1) % p;
}

inline LL C(LL n, LL m) { // m >= n >= 0
    return m < n || n < 0 ? 0 : fac[m] * invf[n] % MOD * invf[m - n] % MOD;
}

LL go(LL l, LL r, LL d) {
    if (l > r) return 0; // trick!
    LL k = r;
    FOR (i, l, r)
        if (h[i] < h[k]) k = i;
    LL len = r - l + 1, height = h[k] - d;
    LL a = go(l, k - 1, h[k]), b = go(k + 1, r, h[k]);
    fill(g, g + len + 1, 0);
    FOR (i, 0, k - l + 1)  // (k - 1) - l + 1
        FOR (j, 0, r - k + 1) // r - (k + 1) + 1
            up(g[i + j], f[a][i] * f[b][j]);
    FOR (i, 0, len + 1)
        FOR (t, 0, i + 1)
             up(f[k][i], g[i - t] * C(t, len - (i - t)) % MOD * C(t, height) % MOD * fac[t]);
    return k;
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    fac_inv_init(M, MOD);
    int n, k;
    cin >> n >> k;
    FOR (i, 1, n + 1) cin >> h[i];
    f[0][0] = 1; // trick!
    cout << f[go(1, n, 0)][k] << endl;
}