msc

题意

给定一张 n(n\leq 2\times 10^5) 个点的完全图和一个序列 {a_n} ，边 (i,j) 的权值为 a_i\oplus a_j ，\oplus 表示异或。求图中一条经过每个点恰好一次的链，使它的最大边权最小。

思路

与 CF888G 相似。将所有点的权插进一棵 01 Trie 中，若两点间有边，则这条边权的首位 1 应该在这两点的 LCA 位置。在 Trie 上找到深度最小的有两个儿子的节点 p ，则不过这个点的路径的影响都可以忽略不计。问题转化为在 p 的两个儿子的子树中找出最小的异或值。一边 DFS 一边贪心地使高位相同即可。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=220000;
const int MAXM=13200000;
const ll INF=2E18;
struct Trie
{
    int nxt[MAXM][2];
    int cnt, root;
    inline void init()
    {
        cnt=0; root=++cnt;
        memset(nxt, 0, sizeof nxt);
    }
    void insert(ll x)
    {
        for (int i=59, p=root; i>=0; i--)
        {
            int t=x>>i&1;
            if (!nxt[p][t]) nxt[p][t]=++cnt;
            p=nxt[p][t];
        }
    }
    int find()
    {
        int p=root;
        while (p)
        {
            if (nxt[p][0]&&nxt[p][1]) return p;
            if (nxt[p][0]) p=nxt[p][0];
            else p=nxt[p][1];
        }
        return 0;
    }
    ll dfs(int u, int v, ll w)
    {
        ll r=INF;
        if (nxt[u][0])
            if (nxt[v][0]) r=min(r, dfs(nxt[u][0], nxt[v][0], w<<1));
            else r=min(r, dfs(nxt[u][0], nxt[v][1], w<<1|1));
        if (nxt[u][1])
            if (nxt[v][1]) r=min(r, dfs(nxt[u][1], nxt[v][1], w<<1));
            else r=min(r, dfs(nxt[u][1], nxt[v][0], w<<1|1));
        return r==INF?w:r;
    }
} trie;
int main()
{
//  freopen("msc.in", "r", stdin);
//  freopen("msc.out", "w", stdout);
    int n;
    scanf("%d", &n);
    trie.init();
    for (int i=1; i<=n; i++)
    {
        ll x; scanf("%lld", &x);
        trie.insert(x);
    }
    int p=trie.find();
    if (!p) puts("0");
    else printf("%lld\n", trie.dfs(trie.nxt[p][0], trie.nxt[p][1], 1));
    return 0;
}

across

题意

一个图有 n+1(n\leq10^6) 个节点，每个节点都有一条通向 0 号节点的边，还有一条通向其他节点的边。对于每个节点，求它走 m(m\leq 10^6) 条边后回到原地的方案数。

思路

从每个节点走到它自己都有两种方式：

• 一直不走通向 0 的边，直到走回原点
• 先随便走若干次，再跳到 0 号节点，从它走到原点

对于第一种方式，可以考虑倍增求出每个点走 m 条边后到达的节点，若能走到自己，就有 1 的贡献；对于第二种方式，前面走的是哪 k 条边没有影响，有 2^k 种方案。预处理出从 0 号点条 i 步到达的节点，两条路径拼接起来即可对这个点贡献。

代码

#include <cstdio>
#include <cstring>
const int MAXN=1100000;
const int MOD=998244353;
int n, m;
int x[MAXN], y[MAXN];
int ans[MAXN];
int qpow(int n, int k)
{
    int r=1;
    while (k)
    {
        if (k&1) r=1ll*r*n%MOD;
        n=1ll*n*n%MOD; k>>=1;
    }
    return r;
}
void mul(int* a, int* b, int* c)
{
    static int t[MAXN];
    for (int i=1; i<=n; i++) t[i]=b[a[i]];
    memcpy(c, t, sizeof t);
}
void qpow(int* a, int* b, int k)
{
    static int t[MAXN];
    memcpy(t, a, sizeof t);
    for (int i=1; i<=n; i++) b[i]=i;
    while (k)
    {
        if (k&1) mul(b, t, b);
        mul(t, t, t); k>>=1;
    }
}
int main()
{
//  freopen("across.in", "r", stdin);
//  freopen("across.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i=0; i<=n; i++) scanf("%d", &x[i]);
    for (int i=0, p=0; i<m; i++, p=x[p])
        ans[p]=(ans[p]+qpow(2, m-i-1))%MOD;
    if (m==0) ans[0]=1;
    qpow(x, y, m);
    for (int i=1; i<=n; i++)
        if (y[i]==i) ans[i]=(ans[i]+1)%MOD;
    for (int i=0; i<=n; i++) printf("%d ", ans[i]);
    putchar('\n');
    return 0;
}

count

题意

给出一棵 n(n\leq 10^5) 个点的树，每个点有点权，要求单点修改 m 次点权，每次修改后询问是否可以通过若干次 将父亲节点的权值分给它的儿子 的操作，使所有点的权值为非负的。

思路

动态 DP 。（并不会）