T1

$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$$ $$xy-n(x+y)=0$$ $$n^2-n(x+y)+xy=n^2$$ $$(n-x)(n-y)=n^2$$ 计算$n^2$的因数个数即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int cc, t[100005], prim[100005], tag[100005], tot;

void euler(int n)
{
    int j;
    for (int i = 2; i <= n; ++i)
    {
        if (!tag[i])
            prim[++tot] = i;
        for (j = 1; j <= tot; ++j)
        {
            if (i * prim[j] > n)
                break;
            tag[i * prim[j]] = 1;
            if (i % prim[j] == 0)
                break;
        }
    }
}

void solve()
{
    cc = 0;
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= tot; ++i)
    {
        if (n % prim[i] == 0)
        {
            t[++cc] = 0;
            while (n % prim[i] == 0)
            {
                t[cc]++;
                n /= prim[i];
            }
        }
    }
    if (n > 1)
        t[++cc] = 1;
    for (int i = 1; i <= cc; ++i)
        t[i] *= 2;
    ll ans = 1;
    for (int i = 1; i <= cc; ++i)
    {
        ans = ans * (t[i] + 1);
    }
    ans = ans / 2 + 1;
    printf("%lld\n", ans);
}

int main()
{
    freopen("equation.in", "r", stdin);
    freopen("equation.out", "w", stdout);
    int t;
    euler(100000);
    cin >> t;
    while (t--)
        solve();
    return 0;
}

T2

定义$dp[i][a][b]$已经在1-i中填了a个左括号，b个右括号的方案数
$$dp[i][a][b]=dp[i-1][a-1][b],dp[i-1][a-1][b-1],dp[i-1][a][b-1],dp[i-1][a][b]$$ $dp2[i][a][b]$表示此时$\sum_{j=1}^i A_j^k$
$$dp2[i][a][b]=dp2[i-1][a][b]+dp[i-1][a][b] \times (a-b)^k$$ $$dp2[i][a][b]=dp2[i-1][a][b]+dp[i-1][a-1][b] \times (a-b)^k$$ 直接由原来的贡献加上$a[i]$的贡献
其余同理
考虑到$n \geq m$时，答案为0，其中$nm \leq 10^5$因此复杂度为$O(nm^2)$，注意优化以下常数即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll mod = 998244353;
ll dp[2][505][505], dp2[2][505][505], tt[505], ans, n, m, k;

ll power(ll x, ll y)
{
    int t = x;
    if (tt[t] != -1)
        return tt[t];
    ll ret = 1;
    while (y)
    {
        if (y & 1)
            ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return tt[t] = ret;
}

int main()
{
    freopen("segment.in", "r", stdin);
    freopen("segment.out", "w", stdout);
    cin >> n >> m >> k;
    if (n >= m)
    {
        puts("0");
        return 0;
    }
    dp[0][0][0] = 1;
    memset(tt, -1, sizeof tt);
    int now = 1;
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 0; j <= n; ++j)
        {
            for (int l = 0; l <= n; ++l)
            {
                if (l > j)
                    continue;
                ll aa = power(j - l, k);
                dp[now][j][l] = dp[now ^ 1][j][l];
                if (j > 0 && l > 0)
                    dp[now][j][l] = (dp[now][j][l] + dp[now ^ 1][j - 1][l - 1]);
                if (j > 0)
                    dp[now][j][l] = (dp[now][j][l] + dp[now ^ 1][j - 1][l]);
                if (l > 0)
                    dp[now][j][l] = dp[now][j][l] + dp[now ^ 1][j][l - 1];
                if (dp[now][j][l] >= mod)
                    dp[now][j][l] %= mod;

                dp2[now][j][l] = dp2[now ^ 1][j][l] + dp[now ^ 1][j][l] * aa;
                if (j > 0 && l > 0)
                    dp2[now][j][l] += dp2[now ^ 1][j - 1][l - 1] + dp[now ^ 1][j - 1][l - 1] * aa;
                if (j > 0)
                    dp2[now][j][l] += dp2[now ^ 1][j - 1][l] + dp[now ^ 1][j - 1][l] * aa;
                if (l > 0)
                    dp2[now][j][l] += dp2[now ^ 1][j][l - 1] + dp[now ^ 1][j][l - 1] * aa;
                if (dp2[now][j][l] >= mod)
                    dp2[now][j][l] %= mod;
            }
        }
        now ^= 1;
    }
    cout << dp2[now ^ 1][n][n] << endl;
    return 0;
}

T3

考虑不进行更改的情况，对于每个节点建立trie树
链： 只建一棵trie树，每个节点记录子树内的最小编号，修改的时候改掉节点的编号(set维护)
100: 树链剖分+链
100: 用线段树划分区间，把操作序列放在线段树的节点上，然后对于每个节点进行操作即可

#include <bits/stdc++.h>
using namespace std;
#define lc (rt << 1)
#define rc ((rt << 1) | 1)

struct node
{
    int Next, y, v;
} Pth[100005];
struct task
{
    int ty, v;
};
struct trie
{
    int cnt, Next[2];
} trie[6000005];
vector<task> tr[400005];
int cnt, head[100005];
void add(int x, int y)
{
    cnt++;
    Pth[cnt].Next = head[x];
    Pth[cnt].y = y;
    head[x] = cnt;
}

void change(int wl, int wr, int rt, int l, int r, task tk)
{
    if (tk.ty == 2 || wl == l && wr == r)
    {
        tr[rt].push_back(tk);
        if (wl == l && wr == r)
            return;
    }
    int mid = (l + r) >> 1;
    if (wr <= mid)
        change(wl, wr, lc, l, mid, tk);
    else if (wl > mid)
        change(wl, wr, rc, mid + 1, r, tk);
    else
        change(wl, mid, lc, l, mid, tk), change(mid + 1, wr, rc, mid + 1, r, tk);
}

int n, m, dfn[100005], num, siz[100005], w[100005], q[100005], ans[100005], aid;

void dfs(int x)
{
    dfn[x] = ++num;
    siz[x] = 1;
    for (int i = head[x]; i; i = Pth[i].Next)
    {
        int y = Pth[i].y;
        dfs(y);
        siz[x] += siz[y];
    }
}

int tot;
void push(int p)
{
    trie[1].Next[0] = trie[1].Next[1] = trie[1].cnt = 0;
    tot = 1;
    for (int i = 0; i < tr[p].size(); ++i)
    {
        task tk = tr[p][i];
        // cout << "task: " << p << ' ' << tk.ty << ' ' << tk.v << endl;
        if (tk.ty == 1)
        {
            int T, v;
            if (tk.v >= 0)
                T = tk.v, v = 1;
            else
                T = -tk.v, v = -1;
            int now = 31, x = 1;
            while (now >= -1)
            {
                trie[x].cnt += v;
                if (now == -1)
                    break;
                if (trie[x].Next[(T >> now) & 1] == 0)
                {
                    trie[x].Next[(T >> now) & 1] = ++tot;
                    trie[tot].cnt = trie[tot].Next[1] = trie[tot].Next[0] = 0;
                }
                x = trie[x].Next[(T >> now) & 1];
                now--;
            }
        }
        else
        {
            int T = q[tk.v], A = 0;
            int now = 31, x = 1;
            while (now >= 0)
            {
                int a = (T >> now) & 1;
                A <<= 1;
                if (trie[trie[x].Next[a ^ 1]].cnt != 0)
                    A |= 1, x = trie[x].Next[a ^ 1];
                else
                    x = trie[x].Next[a];
                now--;
            }
            ans[tk.v] = max(ans[tk.v], A);
        }
    }
}

int main()
{
    freopen("xor.in", "r", stdin);
    freopen("xor.out", "w", stdout);
    cin >> n >> m;
    for (int i = 2; i <= n; ++i)
    {
        int x;
        scanf("%d", &x);
        add(x, i);
    }
    dfs(1);
    for (int i = 1; i <= n; ++i)
    {
        int v;
        scanf("%d", &v);
        w[i] = v;
        change(dfn[i], dfn[i] + siz[i] - 1, 1, 1, n, (task){1, v});
    }
    for (int i = 1; i <= m; ++i)
    {
        int ty;
        scanf("%d", &ty);
        if (ty == 0)
        {
            int x, v;
            scanf("%d%d", &x, &v);
            change(dfn[x], dfn[x] + siz[x] - 1, 1, 1, n, (task){1, -w[x]});
            w[x] = v;
            change(dfn[x], dfn[x] + siz[x] - 1, 1, 1, n, (task){1, w[x]});
        }
        else
        {
            int x;
            scanf("%d", &x);
            change(dfn[x], dfn[x], 1, 1, n, (task){2, ++aid});
            q[aid] = w[x];
        }
    }
    for (int i = 1; i <= (n << 2); ++i)
    {
        if (tr[i].size())
        {
            push(i);
        }
    }
    for (int i = 1; i <= aid; ++i)
    {
        printf("%d\n", ans[i]);
    }
    return 0;
}

DP

保卫王国
Tree chain problem
Crash的旅行计划
有i张卡片，正面的数为ai,反面的数为bi，有m个熊孩子会交换ci,di两个位置上的卡片。每个熊孩子捣乱后，你都需要判断，能否通过翻转卡片上的数从左到右单调不降 线段树上存mi,mx表示该左端点取小值/大值时，右端点的最小值，不存在记-1

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/cxjy-day-12/