A.数字

题意：
给定两个数字 $aa, b$ 求在 $aa$ 前面加连接上一个三位数之后是 $b$ 的倍数有多少种方案

B.网格

题意：
有一个 $n \times n$ 的网格图，求从 $(0, 0)$ 走到 $(n, n)$ 的最小代价
向右或向上走的代价为 $w1$，在 $k$ 个特殊的点可以向右上走，代价为 $w2$
$n \leq 10^9, k \leq 2000$

如果 $w1 * 2 \leq w2$ 那么答案为 $w1 * n * 2$

否则最多可以使用几次 $w2$

每次使用 $w2$ 都会向右上方移动，所以当且仅当 $x_i < x_j$ $and$ $y_i < y_j$ 才可以先后使用 $i, j$ 这两个特殊点

那么就可以 $DP$ 求出最多可以使用特殊点的次数 $cnt$

最终答案为 $(n * 2 - cnt * 2) * w1 + cnt * w2$

时间复杂度 $O(k^{2})$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2020;

int n, k, w1, w2;
PII p[N];
int f[N];

int main()
{
    scanf("%d%d%d%d", &n, &k, &w1, &w2);
    int m = n << 1;
    if(w1 * 2 <= w2)  return 0 * printf("%lld\n", (LL)m * w1);

    for(int i = 0; i < k; i ++)  scanf("%d%d", &p[i].x, &p[i].y);
    sort(p, p + k);

    int cnt = 0;
    for(int i = 0; i < k; i ++)
    {
        if(p[i].x >= n or p[i].y >= n)  continue;
        f[i] = 1;
        for(int j = 0; j < i; j ++)
            if(p[j].x < p[i].x and p[j].y < p[i].y and f[j] + 1 > f[i])  f[i] = f[j] + 1;
        if(f[i] > cnt)  cnt = f[i];
    }
    m -= cnt * 2;
    printf("%lld\n", (LL)m * w1 + (LL)cnt * w2);
    return 0;
}

C.有向无环图

题意：
给定 $K$ 要求构造一个没有重边的有向无环图，使得 $1$ 到 $n$ 的方案数为 $K$
点数不得超过 $N$

测试点 $1~3$ 有 $K < N \leq 1000$
测试点 $4~5$ 有 $N = 66, K \leq 2^{64}$

当 $K < N$ 时，我们可以这样构造

1 -> n
1 -> 2 -> n
1 -> 3 -> n
1 -> 4 -> n
……

总点数为 $K + 1$

考虑一种“完全DAG”
假设共 $n$ 个点从 $1$ 到 $n$ 编号，每个点都向所有编号大于它的点连一条边
这样的图从 $1$ 号点抵达 $i > 1$ 号点的方案数就为 ${2} ^ {i - 2}$

我们知道任何数都可以拆分整 $2$ 的指数之和，那么我们在 $1$ 号点和 $n$ 号点之外构造这样一个图
并把需要的总方案数拆分成 $2$ 的指数即可

时间复杂度 $O(n)$ or ${64}^{2}$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef unsigned long long ULL;

const int N = 2020;

ULL k;
int n;

int main()
{
    scanf("%llu%d", &k, &n);
    if(k < n)
    {
        n = k + 1;
        printf("%d %d\n", n, (n - 2) * 2 + 1);
        printf("%d %d\n", 1, n);
        for(int i = 2; i < n; i ++)
            printf("%d %d\n%d %d\n", 1, i, i, n);
    }
    else
    {
        int p = -1, m = 0;
        for(int i = 63; i >= 0; i --)
        {
            if(k >> i & 1)
            {
                m ++;
                if(p == -1)  p = i;
            }
            if(~p)  m += i + 1;
        }
        int n = p + 3;
        printf("%d %d\n", n, m);

        for(int i = 0; i <= p; i ++)
            for(int j = -1; j < i; j ++)
                printf("%d %d\n", j + 2, i + 2);

        for(int i = p; i >= 0; i --)
            if(k >> i & 1)
                printf("%d %d\n", i + 2, n);
    }
    return 0;
}

D.分数

题意：
给出 $n$，初始有一个长度为 $n$ 的序列，第 $i$ 项为 $\frac{1}{i}$
每次找到 $i$ 最小的且分母不为 $1$ 的数 $\frac{p}{q}$，对序列中的所有数乘以 $q$ 并化简，直到所有数的分母都为 $1$

给出 $a, b$ 每次对序列操作的同时令 $a = a \times q + b$，输出 $a$ $mod$ $2^{32}$ 的结果
$n \leq 8 \times 10 ^ 7$

时间复杂度 $O(n)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 8e7 + 10;

int primes[N / 10], cnt;
bool st[N];

void init(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])  primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            st[i * primes[j]] = true;
            if(i % primes[j] == 0)  break;
        }
    }
}

int n;
unsigned a, b;

int q[N];

int main()
{
    scanf("%d%u%u", &n, &a, &b);
    init(n);

    for(int i = 0; i < cnt; i ++)
    {
        int p = primes[i];
        int j = p;
        while(true)
        {
            q[j] = p;
            if(j <= n / p)  j *= p;
            else  break;
        }
    }

    for(int i = 2; i <= n; i ++)
        if(q[i])  a = a * q[i] + b;
    printf("%u\n", a);
    return 0;
}

E.树数数

题意：
给定一棵 $n$ 个点的，以 $1$ 为根的树，每个点的颜色是黑色或者白色（初始为白）并且有权值
定义 $LCBA(a, b)$ 为点对 $a, b$ 的最近黑色公共祖先，然后进行 $m$ 次操作

操作$Q u$ 询问以 $u$ 为根的子树中所有点对的最近黑色公共祖先的权值和
操作$M u w$ 把点 $u$ 的权值修改为 $w$
操作$F u$ 对点 $u$ 的颜色取反

40%的数据 $n, m \leq 2000$
另外20%的数据保证树是随机生成的
对于100%的数据，$n \leq 2 \times {10}^{5}$ $m \leq 4 \times {10}^{5}$

60分做法

$O(n)$ 预处理每个点为根的子树中有多少点对的 $lca$ 是这个点，记为$times + sz - 1$

$O(n)$ 维护每个点到根节点路径上的最近黑点 $top[u]$（每次修改点颜色暴力遍历子树）

$O(n)$ 每次询问遍历子树，对于每个非叶子节点的点累加 $w[top[u]] \times (times[u] + sz[u] - 1)$

时间复杂度 $O(nm)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;

const int N = 200010, M = N << 1;

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int n, m;
int f[N], w[N], col[N];

int sz[N];
LL times[N];

int dep[N], high;

void dfs(int u)
{
    dep[u] = dep[f[u]] + 1;
    if(dep[u] > high)  high = dep[u];

    sz[u] = 1;
    vector<int> v;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        dfs(j);

        v.push_back(sz[j]);
        sz[u] += sz[j];
    }
    for(int i = 0; i < v.size(); i ++)
        times[u] += (LL)v[i] * (sz[u] - v[i] - 1);
    times[u] /= 2;
    //printf("sz[%d] = %d   times[%d] = %d\n", u, sz[u], u, times[u]);
}

int top[N];         //  到根节点路径上最近的黑点

void dfs3(int u, int t)
{
    top[u] = t;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!col[j])  dfs3(j, t);
    }
}

LL res;
void dfs2(int u)
{
    if(sz[u] > 1)  res += (times[u] + sz[u] - 1) * w[top[u]];
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs2(j);
    }
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);

    for(int i = 2; i <= n; i ++)
    {
        scanf("%d", &f[i]);
        add(f[i], i);
    }
    for(int i = 1; i <= n; i ++)  scanf("%d", &w[i]);

    dfs(1);
    if(high > 10000)  return 0;

    while(m --)
    {
        char op[2];
        int u, c;
        scanf("%s%d", op, &u);
        if(op[0] == 'Q')
        {
            res = 0;
            dfs2(u);
            printf("%lld\n", res);
        }
        else if(op[0] == 'M')
        {
            scanf("%d", &c);
            w[u] = c;
        }
        else
        {
            col[u] ^= 1;
            if(col[u])  top[u] = u;
            else
            {
                int j = u;
                while(j and !col[j])  j = f[j];
                top[u] = j;
            }
            dfs3(u, top[u]);
        }
    }
    return 0;
}