260419 - 260426 以前 x 天

P10540 [THUPC 2024 决赛] 古明地枣的袜子

考虑对序列分块，块内进行等价类分治。然后就是序列最右端不能直接拿后缀最大值更新 \(ans\)，需要找到第一个 \(p\ne n\) 的位置然后在这里用后面的 \(sum\) 更新 \(ans\)。

这种东西可能对序列分块而非操作分块会更有前途，因为操作分块合并两个块需要记录数组的全部值非常困难。

P13828 [Ynoi Easy Round 2026] 寒蝉鸣泣之时·卒

根号分治，\(t\) 比较小的采用树分块，根据向量内积的线性性可以把贡献拆开。

P6794 [SNOI2020] 水池

qoj17408 Score Queries

分三种情况，支配对都很少。

P6776 [NOI2020] 超现实树

qoj1865 Guide Map

qoj9798 Safety First

qoj9800 Crisis Event Meteorite

260421 模拟赛 A

有一个奇数乘奇数大小的网格，面积小于等于 \(1000\)，对每个 \((i,j)\) 满足 \(2\mid i+j\)，都有 \((i,j),(i,j+1),(i+1,j),(i+1,j+1)\) 四个点不能同时选多于两个，同时四连通不能同时选，问方案数。

对较短的一维状压，发现相邻的两个格子要么可以选，要么都不能选，所以状态数只有 \(2^{\frac{\sqrt n}{2}}\)，写轮廓线 dp，时间复杂度再乘一个 \(n\)。

260421 模拟赛 B

给定一棵树，边分为虚边和实边两种。你可以断掉任意条虚边，再连上任意条边，使得得到的仍然是一棵树。请你求出连边方案数，以及所有连边得到的图中，\(1\to n\) 的距离之和。两种方案不同，当且仅当断边集合或者加边集合不同。

\(n\le 1000\)

先考虑第一问，发现没被断掉的边形成若干连通块，那么根据 Prufer 序列其方案数为 \(n^{k-2}\prod sz_i\)。在树上对连通块 dp，其实可以做到线性（不用记当前 \(sz\)）：考虑组合意义，相当于先划分连通块，再在每个连通块中选择一个点。于是只需要记录当前连通块内的点选没选就行。

考虑第二问，发现路径形如跨过若干连通块，于是我们枚举哪些连通块在路径上，连通块内部的贡献等于任选两个点之间的距离之和，外部的贡献等于连通块数量减一。然后还要乘以外面连成树的方案数，就是需要在被路径经过的所有连通块中选择一个点，以及在外面的每个连通块分别选一个点，再乘以 \(n\) 的外部连通块数量次方。

考虑连通块内部的贡献，那我们可以看成是在内部选择两个点，并让之间的边产生贡献，所以也只需要记两个 \(0/1\) 表示子树内选没选起点和终点。

还要去掉 \(1,n\) 在一个连通块内，但是选了多个路径连通块的贡献，这可以通过再跑一遍 dp 解决。

260423 模拟赛 A

称一个无向简单图的权值为满足如下条件的无序三元组 \((i,j,k)\) 的数量：

• \(i,j,k\) 之间连接了恰好两条边；

求 \(n\) 个点且权值不超过 \(m\) 的无向简单图数量。\(n\le 10^4,~m\le 15\)

首先可以通过打表发现，\(n\) 个点的连通图权值要么为 \(0\)（团），要么至少为 \(n-2\)。证明也很容易，\(n=3\) 时显然，否则向一个非团的图中加入一个点至少会产生一个合法三元组。

所以我们只需要对 \(n\le 17\) 的连通块求答案，然后卷起来，剩下的部分用权值为 \(0\) 的团填充，应该是个贝尔数。

直接爆搜过不去，由于我们只关心图的结构，因此可以只枚举最小 bfs 序恰好为 \(1,2,3,\cdots\) 的图。设 \(b_i\) 表示与 \(i\) 相连的最小节点，那么满足条件当且仅当 \(b\) 从 \(2\) 开始单调不降。对于一个一般的图，将它按照 bfs 序重标号，被对应的图统计到。发现一个被枚举到的图可以统计到 \(\frac{(n-1)!}{\prod cnt_i!}\) 个图。

打表

// 打表，只需 (1+eps)s
#include<iostream>
#include<functional>
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;

ll ans[18][16];
int edg[18][18];
int cnt[18];

void dfs(int x, int pre, int sum, ll cof) {
    ans[x - 1][sum] += cof;
    if(x == 18) return;
    cof *= x - 1;
    for(int i = 0; i < pre; i++) edg[i][x] = 0;
    function<void(int, int, int)> dfs2 = [&](int y, int cur, int flag) -> void {
        if(y == x) {
            if(flag) {
                dfs(x + 1, flag, cur, cof / ++cnt[flag]);
                --cnt[flag];
            }
            return;
        }
        int nxt = cur;
        edg[y][x] = 0;
        for(int i = 1; i < y; i++)
            nxt += (edg[i][y] + edg[i][x] + edg[y][x]) == 2;
        if(nxt <= 15) dfs2(y + 1, nxt, flag);
        nxt = cur;
        edg[y][x] = 1;
        for(int i = 1; i < y; i++)
            nxt += (edg[i][y] + edg[i][x] + edg[y][x]) == 2;
        if(nxt <= 15) dfs2(y + 1, nxt, flag ? flag : y);
    };
    dfs2(pre, sum, 0);
}

int main() {

    dfs(2, 1, 0, 1);
    for(int i = 1; i <= 17; i++) {
        for(int j = 0; j <= 15; j++) {
            cout << ans[i][j] << ", ";
        }
        cout << '\n';
    }

    return 0;
}

代码

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e4 + 10;

int MOD;
inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }

int n, m, ans;
int c[N][N], s[N][N], bell[N];
int f[N][16];

int g[18][16];
ll g1[18][16] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 30, 4, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 150, 225, 162, 150, 30, 0, 10, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 975, 1980, 2370, 3780, 5490, 4160, 4038, 1800, 1245, 600, 180, 60},
    {1, 0, 0, 0, 0, 7203, 26460, 28290, 58275, 71295, 116865, 151410, 176575, 203070, 226170, 211393},
    {1, 0, 0, 0, 0, 0, 58940, 338520, 528360, 938560, 1417920, 2256408, 3368890, 4325160, 6389040, 7875336},
    {1, 0, 0, 0, 0, 0, 0, 534348, 4492152, 9502920, 17433360, 31082184, 51360624, 79544304, 117421542, 172655028},
    {1, 0, 0, 0, 0, 0, 0, 0, 5353965, 62513640, 179320680, 340585560, 693732060, 1213637040, 2115423360, 3320276760},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 58920345, 915262920, 3490237800, 7335538980, 16012374840, 30209533200, 56420967900},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 707109810, 14120443260, 69970198320, 169274239200, 389690753760, 799120559160},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9192584778, 229616063820, 1446198080580, 4123825708860, 9984857989392},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128696556443, 3933029376276, 30856356951420, 104799493979180},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1930449202815, 70877099950020, 680321864962740},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 30887189206200, 1341830616038640},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 525082220955864},
};

int main() {

    cin >> n >> m >> MOD;
    s[0][0] = bell[0] = 1; c[0][0] = 1;
    for(int i = 1; i < N; i++) {
        c[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
            s[i][j] = (s[i - 1][j - 1] + (ll)j * s[i - 1][j]) % MOD;
            add(bell[i], s[i][j]);
        }
    }

    for(int i = 1; i <= 17; i++) {
        for(int j = 0; j <= 15; j++) {
            g[i][j] = g1[i][j] % MOD;
        }
    }

    f[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            for(int i1 = 1; i1 <= min(i, 17); i1++) {
                for(int j1 = 1; j1 <= j; j1++) {
                    add(f[i][j], (ll)f[i - i1][j - j1] * g[i1][j1] % MOD * c[i - 1][i1 - 1] % MOD);
                }
            }
        }
    }
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= m; j++) {
            add(ans, (ll)f[i][j] * bell[n - i] % MOD * c[n][i] % MOD);
        }
    }
    cout << ans << '\n';

    return 0;
}

260423 模拟赛 B

给你一个无向简单图和一个常数 \(k\)（\(1\le k\le 7\)），让你对于所有无序点对 \((i,j)\) 求出从 \(i\) 走到 \(j\) 恰好经过 \(k\) 个不重复的点的路径数量。\(n\le 1000,~m\le 5000\)

\(k=7\) 肯定是最困难的。直接 \(O(m^2)\) 暴力枚举路径的头两个 \(u,i\) 和末尾两个 \(j,v\)，中间还剩三个，我们容斥 \(u,v\) 是否在中间的三个中出现过，然后大力分讨即可。时间复杂度是 \(O(m^2)\)。

好像 \(k\) 更大的问题是非常困难的。

260423 模拟赛 C

你有一个 \(1\times n\) 格的网格图，一共有 \(2\times(n+1)\) 个格点，其中最右边的那条竖着的边被去掉，因此一共有 \(3n\) 条边。

给你一些电线，你可以弯折电线但是不能剪断，保证总长度恰好为 \(3n\)。问你能不能恰好覆盖网格图上的所有边。

\(n\le 10^5\)

首先由于是覆盖每条边恰好一次，因此路径数量要不少于奇度点数量的一半，也就是 \(m\ge n\)。猜测这是充要的，先把多出的路径都合并掉，然后尝试归纳地构造，对于一个长度 \(>3\) 的路径，将它分解为 \(len=3+2k+t\)，那么就需要 \(k\) 条 \(1\) 边和 \(t\) 条 \(2\) 边。

然而发现当 \(len\) 是偶数时消耗 \(2\) 边的数量是奇数，因此至少消耗一条 \(2\) 边。如果偶数路径比 \(2\) 边的数量多就不能直接构造了。于是我们把两条偶数路径放到一起构造，发现是可以把两条 \(2\) 边合并成一条 \(1\) 边的，所以就对了。