2024CCPC深圳站组队赛题解

A：一道好题

题目描述

有一个长度为 $n$、初始全为 $0$ 的序列 $a$，另有一个长度为 $n$ 的序列 $b$。目标是通过若干次操作将 $a$ 变成 $b$。

可以执行两种操作：

1. 1 x：将 $a$ 中所有值为 $x$ 的数加 $1$。
2. 2 x：将 $a$ 中下标为 $x$ 的数加 $1$。

不需要最小化操作次数，但操作次数不能超过 $20000$。

输入

第一行一个正整数 $n$，满足 $1 \le n \le 1000$。

第二行 $n$ 个非负整数 $b_1,b_2,\cdots,b_n$，满足 $0 \le b_i \le n$。

输出

第一行输出操作次数 $k$，需要满足 $0 \le k \le 20000$。

之后 $k$ 行，每行输出一种操作。对于 1 x，需要满足 $0 \le x \le n$；对于 2 x，需要满足 $1 \le x \le n$。

分析

一开始尝试过贪心和分块，但容易超过操作次数限制。注意到 $20000$ 大约可以支持 $O(n\log n)$ 级别的构造，因此可以考虑分治。

在区间 $[1,n]$ 中，先把后半部分 $[(n+1)/2,n]$ 依次加一，这样整体会被分成两个不同部分，再配合第一种操作对整段统一加一。递归处理左右两段，就能把操作次数控制在可接受范围内。

核心思路是：用“整体加一”降低单点操作次数，再通过分治把不同值逐层拆开。

I：不定方程

题目描述

给定正整数 $n,k$，求不定方程

$$a^k-b^k=n$$

的正整数解数量。

输入

第一行一个整数 $T$，表示询问数量，满足 $1 \le T \le 20$。

之后 $T$ 行，每行两个整数 $n,k$，表示一次询问，满足 $1 \le n \le 10^{18}$，$3 \le k \le 64$。

输出

对于每一组询问，输出一行一个非负整数，表示答案。

分析

利用恒等式：

$$a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+\cdots+b^{k-1})$$

设 $c=a-b$，也就是 $a=b+c$，带入后得到：

$$(b+c)^k-b^k=n$$

可以看出，$a-b$ 是 $n$ 的一个因子；同时在 $c$ 固定时，$(b+c)^k-b^k$ 关于 $b$ 单调递增。

因此可以枚举 $n$ 的因子，再二分寻找对应的 $b$。由于 $n$ 很大，可以使用 Pollard-Rho 分解质因子，再枚举因子组合。

代码

int n, a[N], c[N];
PII b[N];
vector> op;
void merge(int l, int r, int val)//val：此时整个区间的值
{
    if (b[r].f == val)
        return;
    int mid = l + r + 1 >> 1, now = val;
    if (b[mid].f > val)
    {
        for (int i = mid; i  now)
        merge(mid, r, now);
    merge(l, mid - 1, val);
}
void solve()
{
    cin >> n;
    for (int i = 1; i > a[i], b[i] = {a[i], i};

    sort(b + 1, b + 1 + n);
    merge(1, n, 0);

    cout v[N];
int p[N], ff = 0, q[N], cnt = 0;
bool st[N];

void dfs(int u, int f)
{
    for(int it : v[u])
    {
        if(it == f) continue;
        if(ff) return;
        p[it] = u;
        // cout > n;
    for(int i = 1; i > x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        num[x] ++;
        num[y] ++;
    }
    dfs(1, 0);
    q[cnt + 1] = q[1];
    int cnt1 = 0, cnt2 = 0;
    for(int i = 1; i > n >> q >> m >> k;
    p[0] = 1;
    // p2[0] = 1;
    for(int i = 1; i > s[i];
        int z = s[i].size();
        s[i] = ' ' + s[i];
        for(int j = 1; j > c[i];
        int z = c[i].size();
        c[i] = ' ' + c[i];
        for(int j = 1; j > 1;
                    if(check(l, mid, i, j)) l = mid + 1;
                    else r = mid;
                }
                if(c[i][l] != s[j][l])
                {
                    cnt ++;
                }
                lr = l + 1;
                if(cnt > k) break;
            }
            if(cnt >=1;
    }
    return res;
}
void solve(){
    int m,k;cin>>m>>k;
    for(int i=1,sum=1;i<=k;i++,sum+=m-1,sum%=P){
        int ver=f1[i-1]*qmi(sum,P-2)%P;
        f2[i]=f2[i-1]+ver;
        f2[i]%=P;
        f1[i]=(f1[i-1]+(ver+1)*m%P-ver+P)%P;
    }
    cout<<(f1[k]+f2[k])%P<<"\n";
}