## 寻雾启示
#序列dp #单调队列 #二分
最初我想到的做法是贪心。对于 $t_1\ge t_2$，前若干个铁由于走的路程比较近，因此可以等铁刷出来之后再走。后面就是一次拿多个搭。$t_1<t_2$ 就直接等完了之后一路搭过去。但是这样子需要二分，并且细节非常多，我根本无法处理（况且我根本就不知道正确性）。
烧烤一个小时之后，我偶然发现了对于前 $90\%$ 的数据点有 $m\le 10^3$。欸，$\mathcal O\left(m^2\right)$ 可以拿这么多分？于是我开始考虑 DP。
DP 不需要知道最优决策点具体是哪一个，可以直接枚举后计算取最优值。设 $dp_i$ 表示搭 $i$ 块且最后在 $i$ 位置，所需要的最少时间。我们可以枚举之前的决策点 $j$，然后花 $t_2\times j$ 的时间返回 $0$，等待/不等待第 $i$ 块铁。这个可以通过取 $\max(dp_j+t_2\times j,i\times k)$ 得到。
然后重新回到 $j$ 花费 $t_2\times j$，最后搭到 $i$ 花费 $t_1\times (i-j)$。所以状态转移方程
$
dp_i=\min_{j=0}^{i-1}\left(\max(dp_j+t_2\times j,i\times k)+t_2\times j+t_1\times (i-j)\right)
$
初始 $dp_0=0$。现在我们就成功地获得 $90$ 分了，考虑优化转移。
不难通过定义发现 $dp_i$ 肯定是单调递增的，而 $t_2\times i$ 随 $i$ 增大而增大，所以 $dp_j+t_2\times j$ 随 $j$ 增大而增大，而 $i\times k$ 对于枚举的 $i$ 来说是定值。所以我们可以二分，求出一个分界点，这个分界点右边 $\max$ 的取值为 $dp_j+t_2\times j$，左边 $\max$ 的取值为 $i\times k$。
将式子展开，我们只需要知道 $i\times (k+t_1)+\textcolor{red}{j\times (t_2-t_1)}$ 的最大值和 $i\times t_1+\textcolor{red}{j\times (2t_2-t_1)+dp_j}$ 的最大值。红色是我们维护的内容，黑色的是定值。
- 对于 $\textcolor{red}{j\times (t_2-t_1)}$，根据 $t_1$ 和 $t_2$ 的大小关系选择 $0$ 或者分界点左边第一个即可（或者直接取 $\min$ 省的特殊处理）。
- 对于 $\textcolor{red}{j\times (2t_2-t_1)+dp_j}$，不难发现分界线随着 $i$ 增大而右移，所以这是一个滑动窗口。使用单调队列维护即可。
值得注意的是，由于分界线单调递增，可以单独加个指针维护，所以可以将时间复杂度缩减至 $\mathcal O(n)$。但是我懒得想了写的 `lower_bound`，时间复杂度 $\mathcal O\left(n\log_2 n\right)$。
```cpp
const LL kMaxN = 1e5 + 5;
LL dp[kMaxN], f[kMaxN], t, m, k, t1, t2;
deque<LL> q;
LL calc(LL i) {
return dp[i] + i * (2 * t2 - t1);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> m >> k >> t1 >> t2;
dp[0] = 0;
f[0] = calc(0);
q.clear();
q.push_back(0);
for (LL i = 1; i <= m; i++) {
LL p = lower_bound(f, f + i, i * k) - f;
for (; q.size() && q.front() < p; q.pop_front()) { }
// 注意 t1 和 t2 大小关系，选择更小的那一种（0 或 p-1）
dp[i] = min(p ? min(i * (k + t1), i * (k + t1) + (p - 1) * (t2 - t1)) : (LL)1e18, q.size() ? calc(q.front()) + i * t1 : (LL)1e18);
for (; q.size() && calc(q.back()) >= calc(i); q.pop_back()) { }
q.push_back(i);
cout << dp[i] << ' ';
f[i] = dp[i] + t2 * i;
}
cout << '\n';
}
return 0;
}
```
## 青年晚报
#数学 #组合数学 #找规律 #结论
发现这个变换有些复杂，因为每次变换 $F$ 和 $G$ 的计算方式都不同（一个加导数，一个减导数），并且每次变换之后相当于还要交换一次 $F$ 和 $G$。
$n\le 10^9$，哎呀，肯定是不能模拟的了，考虑拆贡献或矩阵加速。不过数据范围 $m\le 5000$ 肯定是不能矩阵的了，看看能不能 $\mathcal O(m^2)$ 拆贡献。
首先对于 $n$ 为偶数的情况，$F$ 和 $G$ 在变换 $n$ 次后就正好对应了真正的 $F$ 和 $G$，因为交换偶数次后不变，同时可能还会有什么规律等待发掘。对于 $n$ 为奇数，跑偶数的情况后再多算一次即可。
很显然，只有高位会对低位产生贡献，因为导数的 $i$ 次项取决于原函数的 $i+1$ 次项，所以我们考虑计算第 $i$ 为对第 $j$ 位（$j<i$）的贡献，暴力枚举 $(i,j)$ 正好 $\mathcal O(m^2)$。
打标结果如下（每行表示进行了 $2k$ 次操作之后的贡献序列，初始时 $9$ 次项为 $1$，其余为 $0$）：
```cpp
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 -72 0 1
0 0 0 0 0 3024 0 -144 0 1
0 0 0 -60480 0 9072 0 -216 0 1
0 362880 0 -241920 0 18144 0 -288 0 1
0 1814400 0 -604800 0 30240 0 -360 0 1
0 5443200 0 -1209600 0 45360 0 -432 0 1
0 12700800 0 -2116800 0 63504 0 -504 0 1
0 25401600 0 -3386880 0 84672 0 -576 0 1
0 45722880 0 -5080320 0 108864 0 -648 0 1
0 76204800 0 -7257600 0 136080 0 -720 0 1
0 119750400 0 -9979200 0 166320 0 -792 0 1
0 179625600 0 -13305600 0 199584 0 -864 0 1
```
首先通过模拟可以得到先加后减和先减后加得到的贡献是一样的。然后不难发现对于 $i$ 往 $j$ 的贡献，仅当 $i-j$ 为偶数的时候才不为 $0$，并且根据 $\cfrac{i-j}{2}$ 的奇偶性一正一负。
但是我们还是找不到系数的规律呀？从右往左看一看每列的第一不为 $0$ 的项，去掉正负后不难发现是 $9\times 8$、$9\times 8\times 7\times 6$、$9\times 8\times \cdots\times 4$，所以对于 $i$ 到 $j$ 的贡献，第一项为 $\cfrac{i!}{j!}$。
不过下面的项我们还是不知道规律呀？注意到它们都是第一项的倍数，那这个系数是什么呢？猜测它和组合数有关，差不多就相当于在 $n$ 量级元素当中选择 $i-j$ 的量级的元素的组合数（当前位作为导数加到低位，或者直接加过去）。
实测得到是 ${} \left(\begin{array}{}n/2\\(i-j)/2\end{array}\right) {}$。于是就很好搞了，预处理组合数，然后 $\mathcal O\left(m^2\right)$ 算贡献。
最后发现一个问题：$n$ 太大了 $n/2$ 的组合数无法处理。但是 $(i-j)/2$ 比较小，所以直接预处理 $\prod\limits_{k=1}^{(i-j)/2}\left(\cfrac{n}{2}-k+1\right)$ 即可，算的时候乘上 $\left(\cfrac{(i-j)}{2}\right)!$ 的逆元即可。
```cpp
const LL kMaxN = 1e7 + 5, kMod = 1e9 + 7;
LL fac[kMaxN], inv[kMaxN], hke[kMaxN], n, m;
LL pow(LL a, LL b) {
LL res = 1;
for (; b; b /= 2) {
b % 2 && (res = res * a % kMod);
a = a * a % kMod;
}
return res;
}
void init() {
fac[0] = 1;
for (LL i = 1; i < kMaxN; i++) {
fac[i] = fac[i - 1] * i % kMod;
}
inv[kMaxN - 1] = pow(fac[kMaxN - 1], kMod - 2);
for (LL i = kMaxN - 2; i >= 0; i--) {
inv[i] = inv[i + 1] * (i + 1) % kMod;
}
hke[0] = 1;
for (LL i = 1; i <= m; i++) {
hke[i] = hke[i - 1] * (n / 2 - i + 1) % kMod;
}
}
LL comb(LL n, LL m) {
if (m > n) {
return 0;
}
return hke[m] * inv[m] % kMod;
}
void solve(const vector<LL> &f, vector<LL> &res) {
for (LL i = 0; i <= m; i++) {
LL sum = f[i];
for (LL j = i; j >= 0; j -= 2) {
if (i - j > n) {
break;
}
res[j] = (res[j] + comb(n / 2, (i - j) / 2) * sum % kMod) % kMod;
sum = sum * j % kMod * (j - 1) % kMod;
sum = (-sum + kMod) % kMod;
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
init();
vector<LL> f(m + 1), g(m + 1), wyy(m + 1), zrr(m + 1);
for (LL &i : f) {
cin >> i;
}
for (LL &i : g) {
cin >> i;
}
solve(f, wyy);
solve(g, zrr);
if (n % 2) {
for (LL i = 0; i < m; i++) {
wyy[i] = (wyy[i] - (i + 1) * wyy[i + 1] % kMod + kMod) % kMod;
zrr[i] = (zrr[i] + (i + 1) * zrr[i + 1] % kMod + kMod) % kMod;
}
swap(wyy, zrr);
}
for (LL i : wyy) {
cout << i << ' ';
}
cout << '\n';
for (LL i : zrr) {
cout << i << ' ';
}
return 0;
}
```
## 寻宝游戏
#贪心 #ST表 #线段树
没写任何代码，没有什么思路，贪心暴力也不会。去看题解，发现确实是贪心，维护区间最大和严格次大值，等会看看。
## 呼吸之野
#线段树 #二分
采用的可持久化线段树+单调队列判断是否有已经满足条件的区间被包含，但是不知道为什么全 WA 了一分也没有，大分题目。