## 种树
#数学 #质因数分解 #贪心
首先看到乘积、因数这类的，就很难不想到做质因数分解。对于一个正整数 $n$，如果它的唯一质因数分解为 $n=\prod a^k$（$k$ 是质因子 $a$ 在 $n$ 中的出现次数），那么它的因数个数 $\text d(n)=\prod(k+1)$。直观来看就是每个质因数都有 $k+1$ 种取指数的方式。
现在考虑 $w$ 分过来对 $\prod \text d(a_i)$ 的影响。分质因子考虑，枚举质因子，假设其在 $w$ 中的出现次数为 $t$，在 $a_i$ 中的出现次数为 $k_i$，那么相当于你可以对任意 $k_i$ 进行 $t$ 次 $+1$ 操作（分一个质因子过去）。
显然，要最大化 $\prod (k_i+1)$，每次你就把最小的 $k_i\gets k_i+1$ 即可。最终这个质因子对答案的贡献就是 $\prod (k_i+1)$。把所有质因子的贡献都乘起来即可。时间复杂度 $\mathcal O\left(n\sqrt V\right)$。
```cpp
const LL kMaxN = 1e4 + 5, kMod = 998244353;
LL a[kMaxN], n, w, ans = 1;
priority_queue<LL, vector<LL>, greater<>> q;
void solve(LL x, LL k) {
for (LL i = 1; i <= n; i++) {
LL cnt = 0;
for (; a[i] % x == 0; a[i] /= x) {
cnt++;
}
q.push(cnt + 1);
}
while (k--) {
LL x = q.top();
q.pop();
q.push(x + 1);
}
for (; q.size(); q.pop()) {
ans = ans * q.top() % kMod;
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> w;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
}
for (LL i = 2; i * i <= w; i++) {
if (w % i) {
continue;
}
LL cnt = 0;
for (; w % i == 0; w /= i) {
cnt++;
}
solve(i, cnt);
}
if (w > 1) {
solve(w, 1);
}
for (LL i = 1; i <= n; i++) {
for (LL j = 2; j * j <= a[i]; j++) {
if (a[i] % j) {
continue;
}
LL cnt = 0;
for (; a[i] % j == 0; a[i] /= j) {
cnt++;
}
ans = ans * (cnt + 1) % kMod;
}
if (a[i] > 1) {
ans = ans * 2 % kMod;
}
}
cout << ans << '\n';
return 0;
}
```
## 汪了个汪
#构造 #找规律
首先 $t=1$ 的条件完全属于 $t=2$，所以直接走 $[1,n]$ 所组成的无序二元组数量为 $\cfrac{n(n-1)}{2}$，正好对应上了输出的 $\cfrac{n(n+1)}{2}$ 所组成的 $\cfrac{n(n-1)}{2}$ 对相邻二元组。所以所有可能的二元组数量都必须用上。
容易将问题转成图论模型：在 $n$ 个点所组成的双向完全图上，找 $n$ 条简单路径，第 $i$ 条路径长 $i$，每条路径分别从 $1,2,\cdots,n$ 出发，同时互不相等地覆盖了所有的边。
这个问题非常的复杂，我想了两年半才有些许思路。
不难发现在所有二元组 $(i,j)$ 当中，以 $\Delta=|i-j|$ 的大小来分类，$\Delta=1$ 的有 $n-1$ 对，$\Delta =i$ 的有 $n-i$ 对，这正好对应上了跨第 $i$ 列和第 $i+1$ 列的二元组数量是 $n-i$ 个。
所以我们尝试将 $\Delta =i$ 的二元组作用在第 $i$ 列和第 $i+1$ 列当中。具体来说，设某一行第一个数为 $x$，那么这一行的数分别是
$
(x,x\pm 1,x\pm 1\pm 2,\cdots,x\pm 1\pm 2\pm\cdots\pm(n-1))
$
那么我们可以枚举 $x$ 作为每一行的第一个元素。$\pm$ 的话当然是一正一负，这样可以最大化长度。当值超过 $[1,n]$ 的时候，就不用往后继续生成了。
实操下来，对于 $x\in [1,n]$，生成出来的序列长度正好是 $1\sim n$ 的，于是我们按照长度从小到大的顺序输出即可。
> [!tip] 为什么这么生成一定不会产出相同的相邻二元组？
>
> 因为第一个数 $x$ 是不一样的。首先行内肯定不会出现相同二元组，因为所有的 $\Delta$ 都不同。对于某行的第 $j$ 个元素，它所形成的二元组和它正上/下方的 $\Delta$ 相同。它相对于 $x$ 的增量都是 $+1-2\cdots\pm j$ 的，但是由于第一个数 $x$ 不相同，所以和上下的二元组肯定是不同的。所以我们不会生成出相同的相邻二元组。
时间复杂度 $\mathcal O(n^2)$。
```cpp
const int kMaxN = 4005;
int id[kMaxN], n, t;
vector<vector<int>> ans;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> t;
for (int i = 1; i <= n; i++) {
ans.emplace_back();
for (int j = 1, x = i; j <= n; j++) {
ans.back().push_back(x);
if (j % 2) {
x += j;
} else {
x -= j;
}
if (x < 1 || x > n) {
break;
}
}
}
for (int i = 0; i < ans.size(); i++) {
id[ans[i].size()] = i;
}
for (int i = 1; i <= n; i++) {
for (int j : ans[id[i]]) {
cout << j << ' ';
}
cout << '\n';
}
return 0;
}
```
## 挑战 NPC IV
#分治 #贪心
我使用的是暴力。暴力计算 $n!$ 个全排列所对应的答案，然后直接 `nth_element` 求出第 $k$ 大。时间复杂度 $\mathcal O(2^n n)$，成功获得 $12$ 分。
---
然后是赛后改题环节。
首先对于 $k=1$，排序后第 $i$ 个数会在 $i(n-i+1)$ 个区间当中出现过，所以把 $f(i)$ 小的放中间，$f(i)$ 大的放两边即可。
对于 $f(i)$ 一样的，彼此之间怎么排都不会改变答案。所以当 ${} n\ge 29 {}$ 时，最小的答案会出现超过 ${} 10^{18} {}$，此时相当于 $k=1$。
计算方式是令 $cnt_i$ 为 $f(j)=i$ 的数量，求 $\prod cnt_i!$。事实上你求出来 $n=29$ 时应该是大约 $3\times 10^{17}$，这是因为有些不能完全居中，会偏左或偏右，所以实际上这种情况已经超过 $10^{18}$ 了。
所以对于 $n\ge 29$，我们直接考虑 ${} k=1$ 特化的 $\mathcal O\left(\log_2 n\right)$ 做法。直接枚举 $i\in [1,n]$，优先小的的放中间，通过数学计算算出 $i$ 前面的系数并累加。
> [!note] 具体计算方式
>
> 计算 $[l,r]$ 的系数，即 $f(l,r)=\sum\limits_{i=l}^r i(n-i+1)$。
>
> 首先把 $n-i+1$ 拆成 $n+1$ 减去 $i$，应用乘法分配律，得到
>
> $
> 原式=(n+1)\times\sum_{i=l}^r i-\sum_{i=l}^r i^2
> $
>
> 前者应用等差数列求和公式，后者用
>
> $
> \sum_{i=1}^n i=\cfrac{n(n+1)(2n+1)}{6}
> $
>
> 做差即可。得到
>
> $
> 原式=(n+1)\times\cfrac{(l+r)(r-l+1)}{2}-\cfrac{r(r+1)(2r+1)}{6}+\cfrac{(l-1)l(2l-1)}{6}
> $
对于 $n<29$，也是因为最终的答案不超过大约 $10^4$ 这个数量级，所以直接设计状态 $(x_1,x_2,x_3,x_4,x_5,sum)$ 表示 $f(i)=1,2,3,4,5$ 的分别有 $x_1,x_2,x_3,x_4,x_5$ 个，且总优美度为 $sum$ 的合法排列数量。那么我们只需要从小到大枚举 $sum$，计算 $sum$ 对应的数量，就可以找到第 $k$ 小的 $sum$ 了。用记忆化搜索优化常数，规避无用状态。时间复杂度 ${} \mathcal O\left(V\times\prod\limits_{i=1}^{5}\sum\limits_{j=1}^n [f(j)=i]\right) {}$，其中 $V$ 表示答案值域，大约 $10^4$。
## 四暗刻单骑
#贪心 #线段树 #博弈论
我采用的是暴力。令 $1$ 表示当前手可以赢，$0$ 表示不能赢但是可以平局，$-1$ 表示必输。那么爆搜状态 $(i,x,y)$ 就表示当前摸第 $i$ 个牌，当前手手牌为 $x$，对面为 $y$。摸完 $a_i$ 后当前手有两种操作：
1. 不要摸的 $a_i$，直接打出去。
1. $a_i=y$，那么打出去就直接输了，这种情况值为 $-1$。
2. 否则递归计算 $(i+1,y,x)$，然后取反（这就是我的值的特殊性，可以直接取相反数交换状态）。
2. 摸了 $a_i$ 攥手里，把 $x$ 打出去。
1. $x=y$，打出去直接输，值为 $-1$。
2. 否则递归计算 $(i+1,y,a_i)$， 然后取反。
需要注意搞之前先把 $i>r$ 判了（平局），然后把 $a_i=x$ 判了（必胜）。
不难发现对于相同的 $r$，$(i,x,y)$ 所对应答案是一定的，所以可以做记忆化搜索。时间复杂度 $\mathcal O(qnk^2)$。成功获得 $20$ 分。