多校省选模拟 11

我醉(T1)

题意：你有一个 \(N\) 个顶点的树，然后每条边上有一个 \([1,1000]\) 的字符，问这个树上的最长回文串多长。

题解：

这题我好像做过来着，是个经典题目。和下面这道题只有细微差距。

#3241. 「COCI 2019.12」Lampice - 题目 - LibreOJ (loj.ac)

分奇数和偶数二分回文串长度，判断是不是存在使用点分治

现在问题是判断是不是存在一个跨过当前分治重心的长度为 \(len\) 的回文串，可以先扫出来每个联通块中心到根正向/反向的哈希值。

再扫一次联通块里面的每个点，求出来剩下需求的长度 \((len−dep)\) 中是不是有和自己根链上相同哈希值的串，再判断自己根链上剩下的一部分是不是回文串即可。

点分治板子题。

然后复杂度，大概点分治一个 loj，然后之前有个二分答案是 1log，判断是否和自己跟链一样，也是 1log 的。

复杂度大概 \(O(N log ^ 3N)\) 直觉上不能过 \(N=100000\) 的数据，但是因为二分和点分治的常数很小，所以可过。

有个乱搞的做法就是，我们考虑，把每条边拆成两个边和一个点，这样每个回文串都是偶数。

我们只需要枚举中心点的位置，然后两边直接暴力扩展就好了，可以用哈希来维护。

这个玩意可以被菊花图卡掉。菊花图扩展之后是一个长度为 \(2\) 的菊花图。

原因是，我们每次访问深度为 \(1\) 的点的时候，做一次暴力的复杂度为 \(O(N)\)，然后这样的点有 \(O(N)\) 个。。

但是，你可以，整一个，特判。

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::cerr;
using std::pair;
using std::vector;
using std::unordered_map;
using std::tuple;
using std::swap;
using std::random_shuffle;
using std::get;
const int MAXN = 2e5 + 10;
int N, id[MAXN], vis[MAXN], V[MAXN];
vector<pair<int, unsigned long long>> e[MAXN];
unordered_map<unsigned long long, int> mp, flag;
vector<tuple<int, int, unsigned long long>> qjy[2];
auto add_edge = [] (int u, int v, unsigned long long w) {
    e[u].emplace_back(v, w);
    e[v].emplace_back(u, w);
};
template <typename T>
inline T max(const T &x, const T &y) {
    return x > y ? x : y;
}
int solve(int u) {
    vis[u] = u;
    int pre = 0, now = 1;
    qjy[now].clear();
    for (auto &i: e[u]) {
        qjy[now].emplace_back(i.first, i.first, i.second);
        vis[i.first] = u;
    }
    for (int s = 0; s < N; ++s) {
        swap(now, pre);
        qjy[now].clear();
        mp.clear();
        flag.clear();
        for (auto &i: qjy[pre]) {
            if (mp.count(get<2>(i)) && mp[get<2>(i)] != get<1>(i)) {
                flag[get<2>(i)] = 1;
            }
            else {
                mp[get<2>(i)] = get<1>(i);
            }
        }
        for (auto &i: qjy[pre]) {
            if (flag[get<2>(i)]) {
                qjy[now].push_back(i);
            }
        }
        if (qjy[now].empty()) {
            return s;
        }
        swap(now, pre);
        qjy[now].clear();
        for (auto &i: qjy[pre]) {
            unsigned long long val;
            int p, q;
            std::tie(p, q, val) = i;
            for (auto &o: e[p]) {
                if (vis[o.first] != u) {
                    vis[o.first] = u;
                    qjy[now].emplace_back(o.first, q, val * 29 + o.second);
                }
            }
        }
    }
}
int main() {
    freopen("name.in", "r", stdin);
    freopen("name.out", "w", stdout);
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 1, u, v, w; i < N; ++i) {
        cin >> u >> v >> w;
        add_edge(u, N + i, w);
        add_edge(v, N + i, w);
    }
    if (e[1].size() == N - 1) {
        cout << max(solve(1), 1) << '\n';
        return 0;
    }
    int ANS = 1;
    for (int i = 1; i < 2 * N; ++i) {
        V[i] = i;
    }
    for (int i = 1; i < 2 * N && clock() / (double) CLOCKS_PER_SEC < 5.9; ++i) {
        ANS = max(ANS, solve(V[i]));
    }
    cout << ANS << '\n';
    return 0;
}

梧桐依旧(T2)

一道很奇怪的数学题，感觉。

题意：全都在 \(\bmod p\) 意义下进行运算，然后给你两个 \(n\times n\) 的矩阵 \(A,B\)，问满足 \(B\times A=A\) 的矩阵对个数。保证 \(\det(B)\not = 0\)。

题解：感觉好奇怪的转化，十分佩服。

这个题目就是问一个 \(N\times N\) 的矩阵 \(A\)，在一个满秩矩阵 \(B\) 构成的置换群里，作用出来的不动点有多少。

然后，可以直接考虑用 \(\text{BurnSide}\) 引理解决。
\[ \vert X/G\vert=\frac{1}{\vert G\vert}\sum_{g\in G}\vert X^g\vert \]
这是这个定理的数学表达。

我们考虑，这个东西的意思就是：等价类的个数=不动点的总数/群的大小。

那么，我们这道题只需要知道
\[ \vert X/G\vert\times {\vert G\vert} \]
就是答案了。

那么，考虑分开求这两个东西，\(\vert G \vert\) 就是满秩矩阵的个数，这玩意的个数就是 \(\prod _{i=0}^{n-1} p^n - p_i\)，意思就是，你从第一个向量摆到第 \(i\) 个的时候都要保证线性无关，第 \(i\) 个向量可以怎么摆。

然后，我们的重任落到了等价类的个数。

首先一个明显的就是，秩不一样首先会让等价类一样，那么我们可以分秩考虑，就是 \(k\) 个秩时候的答案，然后加起来就行了。

秩为 \(k\) 时候的答案应该是，求 \(B\times A\) 的不同个数来着。就是说，比如我一个秩为 \(k\) 的矩阵，是可以通过先选定 \(k\) 个主向量，然后进行基本矩阵操作之后，变成另一个秩为 \(k\) 的矩阵。

那么答案也就是 \(\frac{\prod_{i=0}^{k-1} p ^ n- p^ i}{\prod _{j=0}^{i-1}p^i-p^j}\)。

最后的答案也就是
\[ \left (\prod_{i=0}^{n-1} p^n-p^i\right)\left(\sum_{i=0}^n\prod_{j=0}^{i-1}\frac{p^n-p^j}{p^i - p^j}\right) \]
。

#include <bits/stdc++.h>
const int N = 3e7 + 10, MOD = 998244353;
int pre[N], suf[N], pw[N], n, p;
auto Mod = [] (int x) -> int {
    if (x >= MOD) {
        return x - MOD;
    }
    else if (x < 0) {
        return x + MOD;
    }
    else {
        return x;
    }
};
int Ksm(int A, int s) {
    int ret = 1;
    for (; s; s /= 2, A = (long long) A * A % MOD) {
        if (s & 1) {
            ret = (long long) ret * A % MOD;
        }
    }
    return ret;
}
int main() {
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    scanf("%d %d", &n, &p);
    pw[0] = 1;
    for (int i = 1; i < N; ++i) {
        pw[i] = (long long) pw[i - 1] * p % MOD;
    }
    int sG = 1;
    for (int i = 0; i < n; ++i) {
        sG = (long long) sG * Mod(pw[n] - pw[i]) % MOD;
    }
    int S = 1;
    pre[0] = suf[n + 1] = 1;
    for (int i = n; i >= 1; --i) {
        suf[i] = (long long) suf[i + 1] * Mod(pw[i] - 1) % MOD;
    }
    pre[n] = Ksm(suf[1], MOD - 2);
    for (int i = n; i > 1; --i) {
        pre[i - 1] = (long long) pre[i] * Mod(pw[i] - 1) % MOD;
    }
    for (int i = 1; i <= n; ++i) {
        S = (S + (long long) pre[i] * suf[n - i + 1]) % MOD;
    }
    printf("%lld\n", (long long) sG * S % MOD);
    return 0;
}

卿且去(T3)

题解：

计算 \(f(S)\) 的时候，有个性质就是说，如果 \(x\) 和 \(2x\) 都在 \(f(S)\) 里，那么肯定选 \(2x\)。

由此可知， \((\lfloor \frac{n}{2} \rfloor,n]\) 的数字一定选，是合法的。那么考虑一手莫比乌斯反演算答案。
\[ f(S)=\sum_{\forall a|x,a\in S}-\mu(x)\left\lceil \frac{\lfloor\frac{N}{x}\rfloor}{2}\right\rceil \]
然后，直接考虑把 \(x\) 的贡献拆出来。一个东西的贡献会被算到当且仅当 \(S\) 中包含他的所有质因子。
\[ \sum f(S)=\sum_{i=2}^n \mu(i)\left\lceil \frac{\lfloor\frac{n}{i}\rfloor}{2}\right\rceil2^{\pi (n)-w(i)} \]
然后 \(2^{-w(i)}\mu(i)\) 是个积性函数，直接 min-25 筛求解即可。

#include <bits/stdc++.H>
const int MAXN = 400005, MAXM = 50000005, MOD = 998244353, iv2 = 499122177;
int add(int x, int y, int p) { return x + y < p ? x + y : x + y - p; }
void Add(int& x, int y, int p) { x = add(x, y, p); }
int Ksm(int A, int s) {
    int ret = 1;
    for (; s; s /= 2, A = (long long) A * A % MOD) {
        if (s & 1) {
            ret = (long long) ret * A % MOD;
        }
    }
    return ret;
}
long long N, A[MAXN], n;
bool vis[MAXN];
int pri[MAXN], G[MAXN], H[MAXN], id1[MAXN], id2[MAXN], ans, tot;
int Id(long long x) { return x <= N / x ? id1[x] : id2[N / x]; }
int main() {
    freopen("yyds.in","r",stdin);
    freopen("yyds.out","w",stdout);
    scanf("%lld", &N);
    n = sqrt(N);
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            pri[++*pri] = i;
        }
        for (int j = 1; j <= *pri && 1ll * i * pri[j] <= n; j++) {
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                break;
            }
        }
    }
    long long nw = 0, lst = 0;
    for (long long l = 1, r; l <= N; l = r + 1) {
        r = N / (N / l);
        A[++tot] = N / l;
        H[tot] = (A[tot] - 1) % MOD;
        G[tot] = (A[tot] - 1) % MOD * (iv2 - 1) % MOD;
        (N / l <= l ? id1[N / l] : id2[l]) = tot;
    }
    for (int j = 1; j <= *pri; j++) {
        for (int i = 1; i <= tot && 1ll * pri[j] * pri[j] <= A[i]; i++) {
            int k = Id(A[i] / pri[j]);
            Add(G[i], add(MOD - G[k], 1ll * (j - 1) * (iv2 - 1) % MOD, MOD), MOD);
            Add(H[i], MOD - H[k] + j - 1, MOD);
        }
    }
    for (int j = *pri; j > 0; j--) {
        for (int i = 1; i <= tot && 1ll * pri[j] * pri[j] <= A[i]; i++) {
            int k = Id(A[i] / pri[j]);
            Add(G[i], 1ll * (iv2 - 1) * add(G[k], MOD - 1ll * (iv2 - 1) * j % MOD, MOD) % MOD, MOD);
        }
    }
    for (long long l = 2, r; l <= N; l = r + 1, lst = nw) {
        r = N / (N / l);
        nw = G[Id(r)],
        Add(ans, 1ll * (N / l - N / 2 / l) % MOD * add(nw, MOD - lst, MOD) % MOD, MOD);
    }
    printf("%d\n", (MOD - 1ll * Ksm(2, H[Id(N)] % (MOD - 1)) * ans % MOD) % MOD);
    return 0;
}