CF edu 188 G 题解 - dk-qwq blog

G. Grid Path #

题意#

大小为 $n \times m$ 的网格，初始在 $(1, 1)$ ，每次可以向左右下移动，求问所有访问方格集合的数量

The only line contains three integers $n$ , $m$ , and $mod$ ( $1 \le n \le 10^8$ ; $1 \le m \le 150$ ; $2 \le mod \le 10^9$ ).

time limit per test: 3 seconds

题解#

每行的访问集合是连续的，所以可以通过 dp 枚举当前行的左右端点来计数

注意到 $n$ 巨大， $m$ 偏小, 显然有写出矩阵方程的 $\Omicron ((m^2)^3 \log n)$ 的做法

考虑优化， dp 转移过程中我们只关注两区间交的位置，但是这样会重复计数，重复计数的区间是连续的，不妨钦定只转移两区间的最左端点（ $\min (l_{last}, l_{cur})$ ），我们记录这个位置是否为某个区间最左端点

则在区间 $[l, r]$ 应该从上一行的 $j \in [l, r], f_{j, 1}$ 1以及 $f_{l, 0}$ 转移

我们还需要对于每一行（ $n$ ）的总和，给矩阵加上一层

我们可以得到如下的转移矩阵

k = 2 * m + 1;
for(int i = 0; i < m; i++) for(int f = 0; f < 2; f++) {
    int u = i * 2 + f;
    for(int l = f? 0: i; l <= i; l++) for(int r = i; r < m; r++) {
        add(trans[u][k - 1], 1);
        for(int j = l; j <= r; j++) {
            int v = j * 2 + (j == l);
            add(trans[u][v], 1);
        }
    }
}

这样得到的矩阵大小是 $k = 2m$ ， $\Omicron (k^ 3\log n) = 7.17 \times 10^8$ ，和 $3 \times 10^8$ 只差常数级别， $2^{64} / 10^9 / 10^9 = 18$ 可以存在 ull 上，每 $18$ 次取模一次

总复杂度 $\Omicron (m^4 + (2 m) ^ 3 \log n)$ ，提交记录

72 collapsed lines
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ull = unsigned long long;
using mat = vector<vector<int>>;
const int K = 305;
int mod;
void add(int &x, int y) {
    x += y;
    if(x >= mod) x -= mod;
}
int k;
ull res[K][K];
int bb[K][K];
mat mul(const mat& a, const mat& b) {
    for(int i = 0; i < k; i++) for(int j = 0; j < k; j++) res[i][j] = 0;

    for(int i = 0; i < k; i++) for(int l = 0; l < k; l++) bb[l][i] = b[i][l];

    for(int i = 0; i < k; i++) for(int l = 0; l < k; l++) {
        for(int j = 0; j < k; j++) {
            res[i][l] += 1ull * a[i][j] * bb[l][j];
            if(j % 18 == 0) {
                res[i][l] %= mod;
            }
        }
        res[i][l] %= mod;
    }

    mat _res(k, vector(k, 0));
    for(int i = 0; i < k; i++) for(int j = 0; j < k; j++) _res[i][j] = res[i][j];

    return _res;
}
mat pow(mat x, int n) {
    mat res(k, vector(k, 0));
    for(int i = 0; i < k; i++) res[i][i] = 1;

    while(n) {
        if(n & 1) res = mul(res, x);
        n >>= 1, x = mul(x, x);
    }
    return res;
}
int n, m;
void solve() {
    cin >> n >> m >> mod;
    k = m * 2 + 1;
    mat base(k, vector(k, 0));

    base[k - 1][k - 1] = 1;
    for(int i = 0; i < m; i++) for(int f = 0; f < 2; f++) {
        for(int l = (f == 1)? 0: i; l <= i; l++) for(int r = i; r < m; r++) {
            add(base[i * 2 + f][k - 1], 1);
            for(int j = l; j <= r; j++) {
                add(base[i * 2 + f][j * 2 + (l == j)], 1);
            }
        }
    }

    mat res = pow(base, n);
    cout << res[1][k - 1] << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    // freopen("A.in", "r", stdin);
    // freopen("A.out", "w", stdout);
    int T = 1;
    // cin >> T;
    while(T--) solve();
}

G. Grid Path#

题意#

题解#

G. Grid Path #