250710 模拟赛

小 D 的划分

给定一棵 \(n\) 个节点的有根树，点有点权 \(a_i,b_i\)。称一条链 \((u,v)\) 为直链当且仅当 \(u\) 是 \(v\) 的祖先。

你需要将这个树划分为若干直链，使得每个节点恰好被划分在一条直链中。现在，你可以任意排列同一条直链内节点的 \(a_i\) 点权。问是否存在一种划分以及重排方案使得最终所有节点 \(a_i=b_i\)。

多测，\(n\le 10^5,\ \sum n\le 10^6\)

注意到划分直链等价于为每个非叶子节点 \(u\) 选择一个儿子 \(v\)，然后描粗 \((u,v)\)。因此不难发现一个节点 \(u\) 只能存在至多 \(1\) 个儿子的子树内部不合法。我们用 multiset 或桶记录当前子树内，多余的数字和缺少的数字。若一棵子树的集合不为空，那么它不合法。稍微转移一下即可。

代码

小 E 爱打表

给定常数 \(n\)，连边 \(x\to (xz) \bmod n\)，边权 \(w=|x-z|\)，求全源最短路。

\(n\le 2010\)

打表后发现答案很小，因此可以减掉一些较长的边，这样用 Dijkstra 跑全源最短路的复杂度就对了。

小 G 爱定义

以下 \(\log\) 均指 \(\lfloor\log\rfloor\)。

给定常数 \(c\ge 1\)，定义 \(f(i)\) 表示小于等于 \(i\) 且最大的数字 \(j\) 满足 \(cj\equiv j\pmod {2^{\log j+1}}\)。

给定大数 \(n\)（\(n\le 2^{10^7}\)），输出 \(\sum_{i=0}^{n}f(i)\bmod 998244353\)。

\(1\le c\le 10{18}\)

注意到

\[ci\equiv i\pmod {2^{\log i+1}}\]

等价于

\[ (c-1)i\equiv 0\pmod {2^{\log i+1}} \]

我们先求出 \(c-1\) 中因子 \(2\) 的次数 \(p\)，然后约束转化为 \(i\) 二进制表示中末端 \(0\) 的数量多于 \(\log i-p+1\)。不难发现这样的 \(i\) 的出现是周期性的，并且每次出现都会贡献一个连续段。因此最后答案形如 \(\log n\) 个等差数列求和。

至于实现细节，先分讨掉 \(c-1=0\) 以及 \(p=0\) 的情况，然后枚举 \(\log i\)，并特判 \(\log i=\log n\) 的贡献即可。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N = 1e7 + 10;
const int MOD = 998244353;

const int inv2 = 499122177;

inline void add(int &a, int b) { a = (a + b) % MOD; }
inline int calc(int bg, int n, int d) { return (2 * bg + (n - 1 + MOD) * d) % MOD * n % MOD * inv2 % MOD; }

char s[N];
int n, p;

int to_int(int l = 0, int r = n - 1) {
    int res = 0;
    for(int i = r; i >= l; i--) res = (res * 2 + (s[i] == '1')) % MOD;
    return res;
}

inline int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int ans;

int pw2[N];

signed main() {

    pw2[0] = 1;
    for(int i = 1; i < N; i++) pw2[i] = pw2[i - 1] * 2 % MOD;

    static int T, c;
    cin >> T;
    while(T--) {
        cin >> s >> c;
        n = ans = 0;
        while(s[n]) ++n;
        reverse(s, s + n);
        --c;
        if(c == 0) {
            int n2 = to_int();
            cout << (1 + n2) * n2 / 2 % MOD << '\n';
            continue;
        }
        if(c & 1) {
            cout << 0 << '\n';
            continue;
        }
        p = 0;
        while(!(c & 1)) { ++p; c >>= 1; }
        if(n == 1) {
            cout << 1 << '\n';
            continue;
        }
        int pwi = 1, pwk = 1;
        for(int i = 0; i < p - 1 && i < n - 1; i++) {
            add(ans, calc(pwi, pwi, 1));
            add(pwi, pwi);
        }
        int c = (1ll << (p - 1)) % MOD;
        for(int i = p - 1; i < n - 1; i++) {
            int k = i - p + 1;
            add(ans, calc(pwi, c, pwk) * pwk % MOD);
            add(pwi, pwi);
            add(pwk, pwk);
        }
        int k = max(0ll, n - p);
        int len = to_int(k, n - 2);
        add(ans, calc(pwi, len, pwk) * pwk % MOD);
        add(ans, to_int(k, n - 1) * pw2[k] % MOD * (to_int(0, k - 1) + 1) % MOD);
        cout << ans << '\n';
    }

    return 0;
}

小 H 要 AK

给定一个 \(n\times m\) 的矩阵 \(a\)，下标从 \(1\) 开始，\(1\le a_{i,j}\le 100\)。给定常数 \(t\)，请你统计矩形中有多少个正方形区域 \((x,y,d)\)（表示以 \((x,y)\) 为左上角，边长为 \(d\) 的正方形区域，\(x+d-1\le n,\ y+m-1\le m\)）满足其中恰好包含 \(t\) 种颜色。

\(n,m\le 1500\)

我们可以为每个位置 \((i,j)\) 维护最小合法边长 \(k_1\) 和最大合法边长 \(k_2\)，然后不难计算答案。

我们可以从右向左扫描，动态维护 \(k_1\)（或 \(k_2\)）。不难注意到从 \((i,j+1)\) 转移到 \((i,j)\) 时，\(k_1\) 和 \(k_2\) 都至多会增加 \(1\)。因此先增加 \(1\)，然后再暴力收缩，复杂度是对的。

那么如何快速收缩和扩展 \(1\) 行或 \(1\) 列呢？我们可以暴力枚举每种颜色，然后用前缀和数组求出其在边界区域内出现的次数，并累加到全局的 cnt 数组即可。时间复杂度 \(O(nmV)\)，空间复杂度 \(O(nmV)\)，空间稍大，无法通过本题。

注意到值域很小，我们可以用 bitset 或 __int128 表示颜色的出现情况，并且可以做到 \(O(1)\) 合并。因此用 st 表维护正方形区域内 bitset 按位或的结果，即可快速查询正方形内颜色数量。时间复杂度 \(O(nm\log n)\)，瓶颈在 st 表。

当值域很小 \(\le 64/128\) 时，我们也许可以通过位运算在 \(O(1)\) 内解决 \(O(V)\) 的问题。

代码

#include<iostream>
#include<bitset>
using namespace std;
const int N = 1510;
const int LOGN = 12;

typedef bitset<128> col_Tp;

int n, m, targ;
int a[N][N];

int lg[N];
col_Tp st[LOGN][N][N];

int calc(int x, int y, int l) {
    int d = lg[l];
    return (st[d][x][y] | st[d][x + l - (1 << d)][y] | st[d][x][y + l - (1 << d)] | st[d][x + l - (1 << d)][y + l - (1 << d)]).count();
}

int mn[N][N], mx[N][N];

int main() {

    for(int i = 2; i < N; i++) lg[i] = lg[i >> 1] + 1;

    cin >> n >> m >> targ;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
            st[0][i][j].set(a[i][j]);
        }
    }

    for(int k = 1; k < LOGN; k++) {
        for(int i = 1; i + (1 << k) - 1 <= n; i++) {
            for(int j = 1; j + (1 << k) - 1 <= m; j++) {
                st[k][i][j] = st[k - 1][i][j] |
                            st[k - 1][i + (1 << (k - 1))][j] |
                            st[k - 1][i][j + (1 << (k - 1))] |
                            st[k - 1][i + (1 << (k - 1))][j + (1 << (k - 1))];
            }
        }
    }

    for(int i = n; i >= 1; i--) {
        int k = 1;
        for(int j = m; j >= 1; j--) {
            if(i + k - 1 < n && j + k - 1 < m) {
                ++k;
            }
            int tmp;
            while(k > 0 && (tmp = calc(i, j, k)) > targ) --k;
            if(tmp == targ) mx[i][j] = k;
            else mx[i][j] = 0;
        }
    }

    for(int i = n; i >= 1; i--) {
        int k = 1;
        for(int j = m; j >= 1; j--) {
            if(i + k - 1 < n && j + k - 1 < m) {
                ++k;
            }
            int tmp;
            while(k > 0 && (tmp = calc(i, j, k)) >= targ) --k;
            mn[i][j] = k + 1;
        }
    }

    long long ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(mx[i][j]) ans += mx[i][j] - mn[i][j] + 1;
        }
    }

    cout << ans << '\n';

    return 0;
}