C、Cells

参考过的题解

题目大意

你有一张无穷大的二维矩阵，你的出发点在格点，并且保证了出发点横坐标依次递增：。

你的目标点分别是，你有几个出发点就有几个目标点，求从出发点去目标点走过的路径没有任何交点的方案数。

Solution

考点：LGV引理+多项式卷积

这题第一个难点就是要会转换模型，他的方案数本质上就是一个LGV引理的模板。

稍微提一下LGV引理，它讲的就是你有起点，目标点，那么你从个起点出发经过完全不相交的边去到个终点的方案数会等于下面的行列式。

对应的是从去往的方案数，那么对应到本题，从去往的方案数就是经典过河卒问题，它的方案数应该是。

写出本题的行列式：

求解阶方阵的常用做法是高斯消元，但是很明显的做法无法通过此题，我们要对这个有特点的行列式做一些初等变换。

我们把这个方阵里面的组合数用阶乘的方式打开，可以得到下面的行列式。

我们发现第列都有我们把他提出外面去得到：

接下来就要作过一定线性代数的题了，要认出这是一个范德蒙德行列式。

具体我们也能推出来，我们假设取了第一行的前三列，我们可以得出下面的这个行列式。

为了好看我们转置一下，并且要知道行列式转置值不变，我们得出下面的这个三行一列行列式，本质上和上面的是一样的。

我们接下来做行初等变换，第二行乘以加到第三行上去，得到

接下来用第一行乘以加到第三行上去，这样我们就得到

接着用第一行乘以加到第二行计算到

这样一个范德蒙德行列式就出来了，我们再把转置之后的行列式每一列提出一个就变成了标准的范德蒙德行列式。

对于后面那个，可以比较自然的想到用多项式乘法计算个数。

构造

那么我们把卷积之后得到的，它的每个指数对应着一个，它的系数就是这个差值出现的次数，由于本题要求的都是符号，所以我们预处理前面的阶乘和分子，后面的我们枚举全部的大于的幂次，做快速幂就可以实现了，还有要注意的两点，第一是实现的时候不能用负数做下标，所以我们要用一个偏移量去处理一下负数，第二本身由于题目给了所以对于相同的来说最多就是个，不会超过个，也不用考虑其他的欧拉降幂去求解快速幂。

综上这题的时间复杂度就在时间内愉快的搞定了，挺好的一道LGV引理题和数学题。

int n;
const int P = 1000001;
int a[500005], jc[500005], inv[500005];

namespace math {
    const int MOD = 998244353;
    inline int add(int x, const int y) { return x += y, x >= MOD ? x - MOD : x; }
    inline int sub(int x, const int y) { return x -= y, x < 0 ? x += MOD : x; }
    inline int mul(const int x, const int y) { return 1ll * x * y % MOD; }
    inline int qpow(int x, int y) {
        int res = 1;
        for (; y; y >>= 1, x = mul(x, x)) if (y & 1) res = mul(res, x);
        return res;
    }
}using namespace math;

namespace NTT {
    int limit;
    int pr = 3; // 能用的ntt的素数原根
    vector<int> A, B, rev;
    void init() {
        int ed = P << 1, bit = -1;
        for (limit = 1; limit <= ed; limit <<= 1) ++bit;
        A.resize(limit); B.resize(limit); rev.resize(limit);
        for (int i = 0; i < limit; ++i)    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bit);
    }
    void ntt(vector<int>& P, int op) {
        for (int i = 0; i < limit; ++i) {
            if (i < rev[i])swap(P[i], P[rev[i]]);
        }
        for (int mid = 1; mid < limit; mid <<= 1) {
            int euler = qpow(pr, (MOD - 1) / (mid << 1));
            if (op < 0)    euler = qpow(euler, MOD - 2);
            for (int i = 0, pos = mid << 1; i < limit; i += pos) {
                int wk = 1;
                for (int j = 0; j < mid; ++j, wk = mul(wk, euler)) {
                    int x = P[i + j], y = mul(wk, P[i + j + mid]);
                    P[i + j] = add(x, y), P[i + j + mid] = add(x, MOD - y);
                }
            }
        }
        if (op > 0)    return;
        int inv = qpow(limit, MOD - 2);
        for (int i = 0; i < limit; ++i)    P[i] = mul(P[i], inv);
    }
    void work() {
        for (int i = 1; i <= n; ++i) A[a[i]] = 1;
        for (int i = 1; i <= n; ++i) B[P - a[i]] = 1;
        ntt(A, 1), ntt(B, 1);
        for (int i = 0; i < limit; ++i)    A[i] = mul(A[i], B[i]);
        ntt(A, -1);
    }
};

int solve() {
    n = read();
    jc[0] = 1;
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        jc[i] = jc[i - 1] * i % MOD;
    }
    inv[n] = qpow(jc[n], MOD - 2);
    for (int i = n - 1; ~i; --i) {
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    }

    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        ans = mul(mul(ans, (a[i] + 1)), inv[i]);
    }
    NTT::init();
    NTT::work();
    for (int i = P + 1; i <= 2 * P; ++i) {
        ans = mul(ans, qpow(i - P, NTT::A[i]));
    }
    print(ans);

    return 1;
}

E、Eyjafjalla

题目大意

你有一颗以为根的个节点的有根树，每个点都有一个温度，并且保证每个父亲到儿子的温度一定是递减的。

现在有次询问，每次询问在点处有一个耐热性为的病毒，问它最多可以散播到多少个点，它可以沿着路径向子孙节点也可以向父亲节点传播，当且仅当存在一个温度，那么这个就不会被传染，并且病毒将在这里被杀死，现在询问最多可以感染多少个节点。

Solution

考点：倍增+dsu+树状数组

我们知道如果对于给出的查询，它不会往上面走就好了，那么这道题就会变得更容易些，这样就变成了我有若干次查询，每次查询某个节点它和它儿子大于的有多少个。其实这是非常容易实现的，我们采用倍增的思想，就可以沿着父亲一路向上找到最后一个小于等于的节点，然后对于简化后的查询我们有下面的做法。

我们只需要从叶子节点往上去维护一个树状数组就可以找到答案，但是很快我们就会发现一个新的问题，我们有了一棵树假设有，那么我们怎么在计算的子树答案的时候把这颗子树带来的贡献屏蔽到呢？主席树？这当然是能做的，也是标答给出的答案，不过我觉得还是接着用之前的树状数组实现比较简单，稍微提一下用主席树如何处理这个问题，我们对于每个节点和它子树构成的区间打上时间戳，接下来就变成了一个可持久化区间查询大于的数，用主席树就可以维护出来了。

但是我就不想用主席树怎么办呢？有另外一个应对树上离线查询很好的方法，就是树上启发式合并(dsu)，它能在的时间应对树上的离线问题，它最广为人知的做法是求解次树上查询点和它子树里面不同的颜色次数有多少种，那么对应到我们这道题，不就是查询和它子树里面大于的有多少个吗？我们可以离散之后用树状数组求解。

那么本题总的时间复杂度就是，这道题好像直接线段树暴力乱搞都能过，应该是数据偏弱了。

放一个线段树暴力查询时间戳的代码。

if (L <= l && r <= R) {
    if (mini[rt] >= v)    return 0;
    if (maxi[rt] < v)    return r - l + 1;
}

下面就是启发式合并的代码，个人认为挺好的一道启发式合并的题目，和模板挺像的，出题人主要想的还是用主席树维护。

const int N = 1e5 + 7;
ll n, m;
int p[N];

vector<int> G[N];

int fa[N][21], son[N], sz[N];
int a[N], b[N * 4], tot;

void dfs(int u, int father) {
    sz[u] = 1;
    fa[u][0] = father;
    for (int i = 1; i <= 20; ++i) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (auto& v : G[u]) {
        if (v == father)    continue;
        dfs(v, u);
        sz[u] += sz[v];
        if (son[u] == 0 || sz[son[u]] < son[v])
            son[u] = v;
    }
}

int ans[N];
vector<pai> query[N];
bool vis[N];

inline int Id(int x) {
    return lower_bound(b + 1, b + 1 + tot, x) - b;
}

int c[N];
inline int lowbit(int x) { return x & (-x); }
inline void add(int i, int x) {
    for (; i <= tot; i += lowbit(i))
        c[i] += x;
}
inline int get(int i) {
    int res = 0;
    for (; i; i -= lowbit(i))    res += c[i];
    return res;
}

void calc(int u, int father) {
    add(Id(a[u]), 1);
    for (auto& v : G[u]) {
        if (v == father || vis[v])    continue; // 注意每个节点只能被计算一次别算多了
        calc(v, u);
    }
}

void delte(int u, int father) {
    add(Id(a[u]), -1);
    for (auto& v : G[u]) {
        if (v == father)    continue;
        delte(v, u);
    }
}

void dsu(int u, int father, bool op) {
    for (auto& v : G[u]) {
        if (v != father && v != son[u])
            dsu(v, u, false);
    }
    if (son[u] != 0) {
        dsu(son[u], u, true);
    }
    vis[son[u]] = true;
    calc(u, father);
    for (auto& [id, l] : query[u]) {
        int pos = Id(l);
        ans[id] = sz[u] - get(pos - 1);
    }
    vis[son[u]] = false;
    if (!op)    delte(u, father);
}

int solve() {
    n = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i)    b[i] = a[i] = read();

    sort(b + 1, b + 1 + n);
    tot = unique(b + 1, b + 1 + n) - (b + 1);

    a[0] = INF64;
    dfs(1, 0);

    m = read();
    for (int i = 1; i <= m; ++i) {
        int x = read(), l = read(), r = read();
        if (a[x] < l || a[x] > r)    ans[i] = 0;
        else {
            for (int k = 20; ~k; --k) {
                if (a[fa[x][k]] <= r)    x = fa[x][k];
            }
            query[x].push_back({ i,l });
        }
    }
    dsu(1, 0, false);

    for (int i = 1; i <= m; ++i)    print(ans[i]);

    return 1;
}

G、Glass Balls

题目大意

你有一颗以为根的有向树，一共有个节点，对于每个节点初始都有一个小球，它存在的每一秒都会向父亲节点滚动一次，然后节点又分为可存储节点和不可存储节点。小球如果到了可存储节点它会掉入节点中，如果有两个小球同时掉入同一个存储节点游戏直接结束答案贡献为。否则对于起点在的小球来说，就是它在能往上滚的次数，求的期望是多少。

Solution

首先我们要找出全部存在贡献的游戏界面是什么。

我们知道任意一个节点它的全部孩子都会向上滚动到它那里去，所以对于合理的游戏局面来说，不能有任何一个节点它两个孩子都是非存储节点，那么这时候这两个孩子带来的球一定会造成崩溃。

所以对于单个节点它合理的概率就是：。即它的儿子中有个不可存储节点或者个不可存储节点的概率。因为这些点选择都是独立事件，所以整棵树构成的合理局面概率为：。

接下来考虑计算滚动次数的期望，我们知道因为它那也去不了，接下来对于它的儿子来说，就有可能往上移动一个步数，也有可能直接就是存储节点，那么我们就要计算是唯一一个合理的非存储节点的概率，其实也很容易计算，对于的父亲来说，合理局面数为，那么选为非存储节点的概率有，做一下除法就是概率了。

所以如果我们假设代表号节点小球的期望，它父亲我们叫做的话，得到下面的转移式。

对于答案来说，我们求解的是期望，如果把当作独立事件的话可以直接求和，不过能发现并不是没关系的，例如两个不同的儿子节点它们的儿子都一起上来了，这种局面下是非法的，所以要乘上总局面合理的概率来调整期望。

时间复杂度，多出来的主要是快速幂求逆元带来的。

const int MOD = 998244353, N = 5e5 + 7;
int qpow(int a, int b) {
    int res = 1;
    a %= MOD;
    for (; b; a = a * a % MOD, b >>= 1)    if (b & 1)    res = res * a % MOD;
    return res;
}
int add(int a, int b) {
    if (a + b >= MOD)    return a + b - MOD;
    return a + b;
}
int inv(int u) {
    return qpow(u, MOD - 2);
}

int p[N], fa[N], sz[N];
vector<int> G[N];
int f[N];

void dfs(int u) {
    f[u] = (1 + f[fa[u]]) * ((1 - p[1] + MOD) % MOD * p[sz[fa[u]] - 1] % MOD) % MOD * inv(add(sz[fa[u]] * (1 - p[1] + MOD) % MOD * p[sz[fa[u]] - 1] % MOD, p[sz[fa[u]]])) % MOD;
    for (auto& v : G[u]) {
        dfs(v);
    }
}

int solve() {
    int n = read(), o = read();
    p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] * o % MOD;
    }
    for (int i = 2; i <= n; ++i) {
        fa[i] = read();
        G[fa[i]].emplace_back(i);
    }

    int P = 1;
    for (int i = 1; i <= n; ++i) {
        sz[i] = G[i].size();
        if (sz[i] == 0)    continue;
        P = P * add(sz[i] * (1 - o + MOD) % MOD * p[sz[i] - 1] % MOD, p[sz[i]]) % MOD;
    }

    for (auto& v : G[1])    dfs(v);

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = add(ans, f[i]);
    }
    ans = ans * P % MOD;
    print(ans);

    return 1;
}

H、Happy Number

题目大意

用构造出第大的十进制数。

Solution

考虑用进制模拟，注意要看作，看作，看作，看作。

int solve() {
    int k = read();
    string s;
    map<int, char> mp;
    mp[0] = '2', mp[1] = '3', mp[2] = '6';
    while(k) {
        --k;
        s += mp[k % 3];
        k /= 3;
    }
    reverse(s.begin(), s.end());
    cout << s << endl;

    return 1;
}

I、Incentive Model

题目大意

两个人一起挖个矿，对于第个矿来说，他有的概率属于，有的概率属于，是当时挖矿前分别持有的股份，任何一个人得到一个矿之后股份会增加，初始的股份为，的股份为，求得到的矿数的期望。

Solution

阅读理解题，好难懂的题意啊，和2021沈阳的那道积分题一模一样，简化题意之后就是一个非常容易的题。

首先我们假设是挖完第个矿后持有的期望股份，我们可以得到下面的式子。

新挖一个矿，两人总股份为，持有的股份为，那么属于的概率就是两者除法，那么增加的股票期望就是乘以增加的。

那么题目要求的期望矿数，也会等于的期望股份减掉除以，即。

当时求不行，我们要考虑优化求解过程，我们把的式子展开。
$ans = \displaystyle \frac{S_n-\frac{x}{y}}{w}=\frac{(1+nw)\frac{x}{y}-\frac{x}{y}}{w}=n\times \frac{x}{y}$

的的确确就是一道阅读理解题…

n,w,x,y = map(int,input().split());
MOD = 998244353
print(n * x * pow(y,MOD-2,MOD) % MOD)