A：一道好题
题目描述
有一个长度为 $n$、初始全为 $0$ 的序列 $a$，另有一个长度为 $n$ 的序列 $b$。目标是通过若干次操作将 $a$ 变成 $b$。
可以执行两种操作：
1 x：将 $a$ 中所有值为 $x$ 的数加 $1$。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$，求不定方程
的正整数解数量。
输入
第一行一个整数 $T$，表示询问数量，满足 $1 \le T \le 20$。
之后 $T$ 行，每行两个整数 $n,k$，表示一次询问，满足 $1 \le n \le 10^{18}$，$3 \le k \le 64$。
输出
对于每一组询问，输出一行一个非负整数，表示答案。
分析
利用恒等式：
设 $c=a-b$，也就是 $a=b+c$，带入后得到：
可以看出，$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";
}