UOJ#884. 【UR #27】509 号迷宫

有一个显然的 \(\mathcal O(n^2)\) DP。

考虑利用组合数优化，只在满足纵坐标 \(y | p\) 的位置记录状态并转移。

有障碍，需要做容斥。

四种转移：线对线、点对点、线对点、点对线

组合计数算明白了就简单了。

代码

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 254500 + 10, MOD = 509, M = MOD + 10;

int n, a[N], f[M][M], c[M][M], fl[N], fr[N], g[N];

// c[n][m] -> C(n + m, m)

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (a[n] == n) {cout << 0; return 0;}
    for (int i = 0; i < MOD; i++) c[i][0] = c[0][i] = 1;
    for (int i = 1; i < MOD; i++) {
        for (int j = 1; j < MOD; j++) c[i][j] = (c[i - 1][j] + c[i][j - 1]) % MOD;
    }
    fill(fl, fl + n + 1, 1);
    for (int l = 0, r = MOD; r <= n; l += MOD, r += MOD) {
        // line to line
        for (int i = MOD; i <= n; i++) fl[i] = (fl[i] + fl[i - MOD]) % MOD;
        for (int i = l + 1; i <= r; i++) {
            // point to point
            for (int j = l + 1; j < i; j++) if (a[j] <= a[i]) {
                g[i] += g[j] * c[i - j][(a[i] - a[j]) % MOD];
            }
            // line to point
            int lim = min(a[i], MOD - (i - l));
            for (int j = 0; j <= lim; j++) g[i] += fl[a[i] - j] * c[i - 1 - l][j];
            g[i] = (MOD - g[i] % MOD);
        }
        // point to line
        for (int i = l + 1; i <= r; i++) {
            int lim = min(n - a[i], MOD - (r - i + 1));
            for (int j = 0; j <= lim; j++) fr[a[i] + j] += g[i] * c[r - i][j];
        }
        for (int i = MOD; i <= n; i++) fr[i] += fr[i - MOD];
        for (int i = 0; i <= n; i++) fl[i] = (fl[i] + fr[i]) % MOD;
        fill(fr, fr + n + 1, 0);
    }
    cout << fl[n] << '\n';
    return 0;
}