题解：P8984 [北大集训 2021] 末日魔法少女计划

· · 题解

太牛了！

首先这个考虑这些矩阵相关的条件是什么意思。

考察矩阵乘法的定义，令 C = A \times B 则有：

C_{i, j} = \sum_{k} A_{i, k} B_{k, j}

再基于 A 矩阵中只有 i \le j 的 A_{i, j} 可能非 0，所以容易联想到区间拼接，那就是：

那么 k = 2 就叫做猫树分治。

对于 k 更大的情况，设计一个多叉树，如果一个节点要分成 B 叉，就要满足：

设计 dp，跑出最优状态就可以了。具体的，设 f_{i, j} 表示，大小为 i 的子树，当前 k = j，m 的最小值即可，我们不妨假设每次都是尽量平均分子树，那么转移比较简单。分步转移，复杂度 O(n^2k)。

// Think TWICE, code ONCE
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll Read() {
    int sig = 1; ll num = 0; char c = getchar();
    while(!isdigit(c)) { if(c == '-') sig = -1; c = getchar(); }
    while(isdigit(c)) num = (num << 3) + (num << 1) + (c ^ 48), c = getchar();
    return num * sig;
}
void Write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) Write(x / 10);
    putchar((x % 10) ^ 48);
}
const int N = 2005, K = 16, inf = 1e9;
int f[K][N], g[K][N], pl[K][N], pr[K][N], q[K][N], a[N][N];
void Construct(int k, int n, vector<int> vec) {
    if(n <= 1) return ;
    if(k == 1) {
        for(auto v : vec) for(auto w : vec) if(w > v) a[v][w] = 1;
        return ;
    }
    int i, j, x = n - pl[k][n] - pr[k][n], y = q[k][x], l, r;
    vector<int> bsiz(1, pl[k][n]);
    for(i = 1; i <= y; i++) bsiz.emplace_back(x / y + (i <= x % y));
    bsiz.emplace_back(pr[k][n]);
    // cerr << "Construct " << k << ' ' << n << " | ";
    // for(auto v : bsiz) cerr << v << ' ';
    // cerr << "| ";
    // for(auto v : vec) cerr << v << ' ';
    // cerr << endl;
    for(i = 0, l = 0; i <= y; l += bsiz[i], i++) {
        r = l + bsiz[i];
        for(j = l; j <= r; j++) a[vec[j]][vec[r]] = 1;
    }
    for(i = 1, l = bsiz[0]; i <= y + 1; l += bsiz[i], i++) {
        r = l + bsiz[i];
        for(j = l; j <= r; j++) a[vec[l]][vec[j]] = 1;
    }
    for(i = 0, l = 0; i <= y + 1; l += bsiz[i], i++) {
        int siz = bsiz[i]; vector<int> nvec; r = l + bsiz[i];
        for(j = l; j <= r; j++) nvec.emplace_back(vec[j]);
        if(i <= y && siz) siz--, nvec.pop_back();
        if(i && siz) siz--, nvec.erase(nvec.begin());
        Construct(k, siz, nvec);
    }
    vector<int> nvec;
    for(i = 1, j = bsiz[0]; i <= y + 1; j += bsiz[i], i++) nvec.emplace_back(vec[j]);
    Construct(k - 2, y, nvec);
}
namespace checker {
    int b[N][N], c[N][N];
    void Check(int n, int k) {
        int i, p, q, r;
        for(p = 0; p <= n; p++) b[p][p] = 1;
        for(i = 1; i <= k; i++) {
            for(p = 0; p <= n; p++) for(q = 0; q <= n; q++) for(r = 0; r <= n; r++) {
                c[p][r] |= b[p][q] && a[q][r];
            }
            memcpy(b, c, sizeof(b)), memset(c, 0, sizeof(c));
        }
        for(p = 0; p <= n; p++) for(q = 0; q <= n; q++) cerr << b[p][q] << (q == n ? '\n' : ' ');
        for(p = 0; p <= n; p++) for(q = p; q <= n; q++) assert(b[p][q]);
    }
}
int main() {
    int i, j, t, n, k; vector<int> vec;
    n = Read(), k = Read(), g[1][1] = g[2][1] = inf;
    for(i = 3; i <= k; i++) q[i][1] = 1;
    for(i = 2; i <= n; i++) {
        f[1][i] = g[1][i] = (i - 1) * i / 2;
        for(j = 2; j <= k; j++) {
            f[j][i] = g[j][i] = inf;
            for(t = 1; t <= i; t++) {
                if(t * 2 <= i) {
                    int val = (f[j][t - 1] + t - 1) * 2 + g[j][i - t * 2];
                    if(f[j][i] > val) f[j][i] = val, pl[j][i] = pr[j][i] = t;
                }
                if(t * 2 + 1 <= i) {
                    int val = (f[j][t - 1] + f[j][t] + t * 2 - 1) + g[j][i - t * 2 - 1];
                    if(f[j][i] > val) f[j][i] = val, pl[j][i] = pr[j][i] = t, pr[j][i]++;
                }
                if(j > 2) {
                    int val = f[j - 2][t];
                    val += (f[j][max(i / t - 2, 0)] + max(0, i / t * 2 - 3)) * (t - i % t);
                    val += (f[j][max(i / t - 1, 0)] + max(0, i / t * 2 - 1)) * (i % t);
                    if(g[j][i] > val) g[j][i] = val, q[j][i] = t;
                }
            }
        }
    }
    for(i = 0; i <= n; i++) a[i][i] = a[i][i + 1] = 1, vec.emplace_back(i);
    int m = 0; vector<pair<int, int> > res; Construct(k, n, vec);
    for(i = 0; i <= n; i++) for(j = i + 2; j <= n; j++) if(a[i][j]) m++, res.emplace_back(i, j);
    Write(m), putchar('\n');
    for(auto v : res) Write(v.first), putchar(' '), Write(v.second), putchar('\n');
    // checker::Check(n, k);
}