251216 模拟赛

T1

给定正整数 \(n\)，\(n\) 共有 \(m\) 个不同的因数 \(x_{1\sim m}\)。考虑一个 \(m\times m\) 的矩阵 \(A_{i,j}=\gcd(x_i,x_j)\)，请你求出 \(A\) 的行列式。

输入是给定 \(n\) 的唯一分解 \(n=\prod_{i=1}^{t}p_i^{k_i}\)，其中 \(p_i\) 表示第 \(i\) 个质数。

\(t\le 5\times 10^5,~k_i\le 10^9\)

考虑 LU 分解，考虑欧拉反演：\(\gcd(x_i,x_j)=\sum_{d|x_i\wedge d|x_j}\varphi(d)\)，那么原矩阵可以表示为：

\[ A_{i,j}=\gcd(x_i,x_j)=\sum_{d|x_i\wedge d|x_j}\varphi(d)=\sum_{k=1}^{m}[x_k|x_i][x_k|x_j]\varphi(x_k) \]

于是构造矩阵

\[ B_{i,j}=[x_i|x_j]\sqrt{\varphi(x_i)} \]

那么有 \(A_{i,j}=\sum_{k=1}^{m}B_{k,i}B_{k,j}\)，那么 \(A=B^TB\)，因此 \(|A|=|B^TB|=|B|^2\)。由 \(B\) 的定义可以得到 \(|B|^2=\prod_{i=1}^{m}\varphi(x_i)\)。于是统计每个质因子的贡献，可以得到式子。

这里提供一种可行的打表思路：考虑将矩阵按某个质因子的次数分块，然后高斯消元，根据上三角分块矩阵的行列式公式，可以将 \(n=p^k\) 的情况推广，得到的式子同上。

T2

给定字符串 \(s\)，称一个有序字符串对 \((a,b)\) 是合法的，当且仅当：

• \(a,b\) 都是 \(s\) 的非空子串；
• 存在一个可以为空的字符串 \(c\)，满足 \(a\) 在 \(s\) 中每一次出现，后面都跟着 \(cb\)；\(b\) 每次出现，前面都跟着 \(ac\)；

请你对 \((a,b)\) 计数。\(|s|\le 10^6\)

虽然出题人希望我们做到线性，但是单 \(\log\) 显然能过。

考虑 SAM，我们要求 \(a,b\) 的 \(\operatorname{endpos}\) 集合必须恰好相差一个常数。记 \(\operatorname{endpos}(a)\) 的最小值为 \(offset(a)\)，那么我们还要求 \(offset(b)\in [offset(a)-len(a),offset(a)-mnl(a)]\)，其中 \(len\) 和 \(mnl\) 分别表示当前等价类的最长和最短长度。于是对 \(\operatorname{endpos}\) 集合进行哈希，相同的跑一遍数点即可。

注意模数为 \(2^{61}-1\) 时底数不能取 \(2\)。

代码

#include<iostream>
#include<algorithm>
#include<cassert>
#define ull unsigned long long
#define lll __int128
#define ll long long
using namespace std;
const int N = 2e6 + 10;
const ull MOD = (1ull << 61) - 1;
const int MOD2 = 998244353;

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

struct myPair {
    int len, mnl, off;
    ull hsh;
    inline bool operator<(const myPair &b) const {
        return hsh < b.hsh;
    }
} a[N], buf[N]; int top;

struct Edge {
    int v, next;
} pool[N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

ull pw[N];
struct Node {
    int chd[26];
    int fa, len;
    inline void clear() {
        for(int i = 0; i < 26; i++) chd[i] = 0;
        fa = len = 0;
    }
} sam[N];
int nn = 1, lst = 1;
ull hsh[N]; int off[N];

void insert(int c) {
    int cur = ++nn, p = lst; sam[cur].clear();
    sam[cur].len = sam[lst].len + 1;
    off[cur] = sam[cur].len;
    hsh[cur] = 1;
    while(p && !sam[p].chd[c]) {
        sam[p].chd[c] = cur;
        p = sam[p].fa;
    }
    if(!p) {
        sam[cur].fa = 1;
    } else {
        int q = sam[p].chd[c];
        if(sam[q].len == sam[p].len + 1) {
            sam[cur].fa = q;
        } else {
            int nq = ++nn; sam[nq].clear();
            sam[nq].len = sam[p].len + 1;
            for(int i = 0; i < 26; i++) sam[nq].chd[i] = sam[q].chd[i];
            sam[nq].fa = sam[q].fa;
            sam[q].fa = sam[cur].fa = nq;
            while(p && sam[p].chd[c] == q) {
                sam[p].chd[c] = nq;
                p = sam[p].fa;
            }
        }
    }
    lst = cur;
}

void dfs(int u) {
    if(!off[u]) off[u] = N;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        dfs(v);
        off[u] = min(off[u], off[v]);
    }
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        hsh[u] = (hsh[u] + (lll)hsh[v] * pw[off[v] - off[u]]) % MOD;
    }
}

int n, ans;
string s;

namespace BIT {
    int s1[N], s2[N];
    int sta[N], top;
    inline void insert(int p, int v) {
        for(int i = p + 1; i <= n + 2; i += i & -i) add(s1[i], v), add(s2[i], (ll)p * v % MOD2);
        sta[++top] = p;
    }
    inline int query(int l, int r, int v) {
        int res = 0;
        for(int i = r + 1; i; i -= i & -i) add(res, ((ll)s1[i] * v - s2[i] + MOD2) % MOD2);
        for(int i = l; i; i -= i & -i) add(res, MOD2 - ((ll)s1[i] * v - s2[i] + MOD2) % MOD2);
        return res;
    }
    inline void clear() {
        while(top) {
            for(int i = sta[top] + 1; i <= n + 2; i += i & -i) s1[i] = s2[i] = 0;
            top--;
        }
    }
}

int main() {

    // freopen("string.in", "r", stdin);
    // freopen("string.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

    sam[1].clear();

    pw[0] = 1;
    for(int i = 1; i < N; i++) pw[i] = (lll)pw[i - 1] * 114514 % MOD;

    cin >> s;
    n = s.size();
    for(int i = 0; i < s.size(); i++) insert(s[i] - 'a');

    for(int i = 2; i <= nn; i++) addEdge(sam[i].fa, i);
    dfs(1);

    for(int i = 2; i <= nn; i++) {
        a[i - 1] = {sam[i].len, sam[sam[i].fa].len + 1, off[i], hsh[i]};
    }

    sort(a + 1, a + nn);
    a[nn].hsh = 0;
    for(int i = 1; i <= nn; i++) {
        if(a[i].hsh != a[i - 1].hsh) {
            BIT::clear();
            for(int j = 1; j <= top; j++) {
                myPair cur = buf[j];
                add(ans, BIT::query(cur.off - cur.len, cur.off - cur.mnl, cur.off - cur.mnl + 1));
                BIT::insert(cur.off, cur.len - cur.mnl + 1);
            }
            BIT::clear();
            for(int j = top; j >= 1; j--) {
                myPair cur = buf[j];
                add(ans, BIT::query(cur.off - cur.len, cur.off - cur.mnl, cur.off - cur.mnl + 1));
                BIT::insert(cur.off, cur.len - cur.mnl + 1);
            }
            top = 0;
        }
        buf[++top] = a[i];
    }

    cout << ans << '\n';

    return 0;
}

T3

数轴上有 \(n\) 棵树，每棵树的高度初始为 \(0\)。你可以花费 \(1\) 的代价将某一棵树的高度增加或减少 \(1\)，或者花费 \(c\) 的代价对任意一个区间的高度增加或减少 \(1\)。给定序列 \(a_{1\sim n}\)，问使得每棵树的高度最终都为 \(a_i\) 的最小代价。

给定 \(m\)，现在每个 \(a_i\) 的取值会在给定的可重集 \(s_i\) 里面等概率均匀随机选取一个值。问最小代价的期望。

\(n\le 100,~c\le n,~m\le 70,~a_i\le 10^9\)

考虑如何解决最优化问题。首先可以证明没有区间减法，具体先说明减出负数是无伤大雅的，因为我们可以把加法都挪到前面；然后所有有区间减法的情况都可以调整为没有区间减法的情况，就对了。

考虑 dp，设 \(f_{i,j}\) 表示前 \(i\) 个数字，还有 \(j\) 次区间加法在延续，最小总代价。考虑转移：

\[ f_{i,j}\gets f_{i-1,k}+c\max(0,j-k)+|a_i-j| \]

然后发现形如卷一个凸壳再加一个凸壳，因此 dp 数组总是下凸的。考虑 slope trick，维护斜率变化的点，一次转移形如删掉左右两个点，再插入两个 \(a_i\)。也可以看成是，初始有 \(c\) 个 \(0\)，然后每次转移形如插入两个 \(a_i\) 再删掉两个点，其中删点操作不影响最小值。考虑维护最小值，记一次插入 \(a_i\) 之后的一个最小值点为 \(p\)，可以说明在插入 \(a_i\) 之前 \(p\) 就是一个最小值点，那么最小值会上升 \(a_i-p\)（可以说明 \(p\le a_i\)）。

因此考虑计算 \(\sum a_i-p\)，其中 \(\sum a_i\) 是简单的。对于 \(\sum p\)，考虑这么一件事：每删除序列左侧的一个点，就说明它一定是一个 \(p\)。由于删数是和值域排名有关的，于是可以想到把贡献拆到 \(\ge x\) 的数被删了多少个。然后记 \(g_{i,j}\) 表示前 \(i\) 个数，\(\ge x\) 的数还剩 \(j\) 个。然后转移需要记一下方案数，总之是容易的。时间复杂度 \(O(n^2mc)\)。

代码

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N = 110;
const int M = 72;
const int MOD = 1e9 + 7;

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;
}

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

int n, m, c, x, ans;
int a[N][M];

int num[N * M], nn;
int f[N][N], g[N][N];

int calc() {
    f[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        int c0 = 0, c1 = 0;
        for(int j = 1; j <= m; j++) {
            if(a[i][j] >= x) c1++;
            else c0++;
        }
        for(int j = 0; j <= c; j++) f[i][j] = g[i][j] = 0;
        for(int j = 0; j <= c; j++) {
            add(g[i][max(0ll, j - 1)], g[i - 1][j] * c0 % MOD);
            add(f[i][max(0ll, j - 1)], f[i - 1][j] * c0 % MOD);
            if(j == c) {
                add(g[i][j], (g[i - 1][j] + f[i - 1][j]) * c1 % MOD);
                add(f[i][j], f[i - 1][j] * c1 % MOD);
            } else {
                add(g[i][j + 1], g[i - 1][j] * c1 % MOD);
                add(f[i][j + 1], f[i - 1][j] * c1 % MOD);
            }
        }
    }
    int res = 0;
    for(int i = 0; i <= c; i++) add(res, g[n][i]);
    return res;
}

signed main() {

    cin >> n >> m >> c;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
            num[++nn] = a[i][j];
            add(ans, a[i][j]);
        }
    }

    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);

    ans = ans * qpow(m, n - 1) % MOD;

    for(int i = 1; i <= nn; i++) {
        x = num[i];
        add(ans, MOD - calc() * (num[i] - num[i - 1]) % MOD);
    }
    cout << ans * qpow(qpow(m, MOD - 2), n) % MOD << '\n';

    return 0;
}