今天被各路神仙吊打，顺利 gg。

A – Forging 锻造

在考场上我推了个有后效性的 DP，还以为是高斯消元，然后看到数据范围就 GG 了。这道题主要是把一些东西给转换掉了。

首先，对一个概率为\(p\)的事件，它的期望次数是\(\frac{1}{p}\)（参见这里）。然后，考虑一个状态\(dp[i]\)代表合成第\(i\)级武器的期望花费。显然\(dp[0] = a\)。

考虑\(dp[1]\)的求法，首先需要两个级别为\(0\)的武器，然后发现无论失败与否都可以保证至少又一个\(0\)级武器，所以我们只需要注意另外一个武器的花费就可以了：

\[ dp[1] = dp[0] + dp[1] \times \frac{1}{p} \]

也就是说，第一件武器的贡献在任何概率下都存在，即使失败也会至少存在一个武器；对于另外一件武器，考虑乘上它成功的次数就行了。

我们现在考虑\(i \geq 2\)的情况。首先，\(i – 2\)级别的武器永远存在，所以不需要乘系数，\(i – 1\)级别的武器锻造成功的次数也是\(\frac{1}{p}\)，所以：

\[ dp[i] = dp[i – 1] * \frac{1}{p} + dp[i – 2] \]

这道题就没了，现在感觉有点傻逼。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e7 + 20, mod = 998244353;

int b[MAX_N], c[MAX_N], n, a, bx, by, cx, cy, p, inv[MAX_N], max_range, dp[MAX_N];

int main()
{
    freopen("forging.in", "r", stdin);
    freopen("forging.out", "w", stdout);
    scanf("%d%d%d%d%d%d%d", &n, &a, &bx, &by, &cx, &cy, &p);
    b[0] = by + 1, max_range = max(max_range, b[0]);
    c[0] = cy + 1, max_range = max(max_range, c[0]);
    for (int i = 1; i < n; i++)
    {
        b[i] = ((long long)b[i - 1] * bx + by) % p + 1, max_range = max(max_range, b[i]);
        c[i] = ((long long)c[i - 1] * cx + cy) % p + 1, max_range = max(max_range, c[i]);
    }

    inv[1] = 1;
    for (int i = 2; i <= max_range; i++)
        inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;

    dp[0] = a;
    dp[1] = 1LL * (a + 1LL * inv[min(b[0], c[0])] * c[0] % mod * a % mod) % mod;
    for (int i = 2; i <= n; i++)
        dp[i] = (1LL * dp[i - 1] * inv[min(b[i - 2], c[i - 1])] % mod * c[i - 1] % mod + dp[i - 2]) % mod;
    printf("%d", dp[n]);
    return 0;
} // A.cpp

B – Division 整除

他直接给了你\(n\)的单次质因子，所以会想到 CRT。考虑在各个素数域内进行线性筛来筛积性函数\(x^m\)，然后统计\(x^m \equiv x \ (mod p_i)\)的个数，然后把答案乘起来就可以了。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 55, mod = 998244353;

int id, T, c, ci[MAX_N], m, func[12000], primes[12000];
bool isPrime[10001];

inline int read()
{
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline int quick_pow(int bas, int tim, int modulo)
{
    int ans = 1;
    bas %= modulo;
    while (tim)
    {
        if (tim & 1)
            ans = 1LL * ans * bas % modulo;
        bas = 1LL * bas * bas % modulo;
        tim >>= 1;
    }
    return ans;
}

inline int sieve(int n)
{
    int ans = 2;
    for (register int i = 2; i <= n - 1; i++)
    {
        if (!isPrime[i])
            func[i] = quick_pow(i, m, n);
        for (register int j = 1; j <= n - 1; j++)
        {
            if (i * primes[j] > n)
                break;
            func[i * primes[j]] = func[i] * func[primes[j]] % n;
            if (i % primes[j] == 0)
                break;
        }
        ans += func[i] == i;
    }
    return ans;
}

int main()
{
    /*
    freopen("division.in", "r", stdin);
    freopen("division.out", "w", stdout);
    */

    int tot = 0;
    for (register int i = 2; i <= 10000; i++)
    {
        if (!isPrime[i])
            primes[++tot] = i;
        for (register int j = 1; j <= tot; j++)
        {
            if (i * primes[j] > 10000)
                break;
            isPrime[i * primes[j]] = true;
            if (i % primes[j] == 0)
                break;
        }
    }

    id = read(), T = read();
    while (T--)
    {
        int ans = 1;
        c = read(), m = read();
        for (register int i = 1; i <= c; i++)
            ci[i] = read(), ans = 1LL * ans * sieve(ci[i]) % mod;
        printf("%d\n", ans);
    }
    return 0;
} // B.cpp

C – Money 欠钱

这道题大力 LCT 就行了。中间要注意只有深度严格单调的链才能被统计，且必须注意进行

// C.cpp
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
#define lson ch[p][0]
#define rson ch[p][1]

using namespace std;

const int MAX_N = 1e5 + 200, INF = 0x3f3f3f3f;

int ch[MAX_N][2], fa[MAX_N], val[MAX_N], minVal[MAX_N], revTag[MAX_N];
int size[MAX_N], n, m, mem[MAX_N], sta[MAX_N];

#define rint register int

void write(int x){
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

inline char nc()
{
    static char buf[100001], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int read()
{
    rint num = 0;
    char c;
    while (isspace(c = nc()))
        ;
    while (num = num * 10 + c - 48, isdigit(c = nc()))
        ;
    return num;
}

inline bool isRoot(rint p)
{
    return ch[fa[p]][0] != p && ch[fa[p]][1] != p;
}

inline int check(rint p) { return ch[fa[p]][1] == p; }

inline void clear(rint p) { lson = rson = fa[p] = val[p] = size[p] = revTag[p] = minVal[p] = 0; }

inline void pushUp(rint p)
{
    clear(0);
    size[p] = 1 + size[lson] + size[rson];
    minVal[p] = val[p];
    if (lson)
        minVal[p] = min(minVal[p], minVal[lson]);
    if (rson)
        minVal[p] = min(minVal[p], minVal[rson]);
}

inline void pushDown(rint p)
{
    if (revTag[p])
    {
        if (lson)
            revTag[lson] ^= 1, swap(ch[lson][0], ch[lson][1]);
        if (rson)
            revTag[rson] ^= 1, swap(ch[rson][0], ch[rson][1]);
        revTag[p] = 0;
    }
}

inline void update(rint x)
{
    rint tot = 0;
    sta[++tot] = x;
    while (!isRoot(x))
        x = fa[x], sta[++tot] = x;
    while (tot)
        pushDown(sta[tot--]);
}

inline void rotate(rint x)
{
    rint y = fa[x], z = fa[y], dir = check(x), w = ch[x][dir ^ 1];
    fa[x] = z;
    if (!isRoot(y))
        ch[z][check(y)] = x;
    ch[y][dir] = w, fa[w] = y;
    ch[x][dir ^ 1] = y, fa[y] = x;
    pushUp(y), pushUp(x), pushUp(z);
}

inline void splay(rint x)
{
    update(x);
    for (rint fat = fa[x]; fat = fa[x], !isRoot(x); rotate(x))
        if (!isRoot(fat))
            rotate(check(fat) == check(x) ? fat : x);
}

inline int access(rint x)
{
    rint fat = 0;
    for (; x != 0; fat = x, x = fa[x])
        splay(x), ch[x][1] = fat, pushUp(x);
    return fat;
}

inline void makeRoot(rint p)
{
    access(p), splay(p);
    swap(lson, rson), revTag[p] ^= 1;
}

inline int find(rint p)
{
    access(p), splay(p);
    while (lson)
        p = lson;
    splay(p);
    return p;
}

inline void link(rint x, rint y)
{
    makeRoot(x);
    if (find(y) == x)
        return;
    fa[x] = y;
}

inline void split(rint x, rint y)
{
    makeRoot(x);
    access(y), splay(y);
}

inline int lca(rint x, rint y)
{
    access(x);
    return access(y);
}

inline int findFa(rint x) { return mem[x] == x ? x : mem[x] = findFa(mem[x]); }

int main()
{
    /*
    freopen("money.in", "r", stdin);
    freopen("money.out", "w", stdout);
    */

    rint lastans = 0;
    n = read(), m = read();
    for (rint i = 1; i <= n; i++)
        mem[i] = i, val[i] = minVal[i] = INF;
    while (m--)
    {
        rint opt, a, b, c;
        opt = read(), a = read(), b = read();
        a = (a + lastans) % n + 1;
        b = (b + lastans) % n + 1;
        if (opt == 0)
        {
            c = read(), c = (c + lastans) % n + 1;
            mem[findFa(a)] = findFa(b);
            val[a] = minVal[a] = c;
            link(a, b);
        }
        else
        {
            if (findFa(a) != findFa(b))
            {
                write(lastans = 0), puts("");
                continue;
            }
            if (lca(a, b) == b)
            {
                rint root = findFa(b);
                split(a, b);
                write(lastans = minVal[ch[b][0]]), puts("");
                makeRoot(root);
            }
            else
                write(lastans = 0), puts("");
        }
    }
    return 0;
}