A 小月的材料
知识点：模拟、绝对值
直接按定义计算 $3$ 段差值并加权即可：
$$\mathrm{ans}=4|a-b|+2|b-c|+|c-a|。$$
时间复杂度 $\mathcal{O}(1)$。
void solve() {
int a, b, c;
cin >> a >> b >> c;
cout << 4 * abs(a - b) + 2 * abs(b - c) + abs(c - a) << endl;
}B 小月的点歌台
知识点：字符串、计数、模拟
从左到右扫描字符串。处理第 $i$ 次点歌时，将对应类别的计数加一；第 $1$ 次使计数达到 $3$ 的位置就是答案。若扫描结束仍没有类别达到 $3$ 次，则输出 $-1$。
时间复杂度 $\mathcal{O}(n)$。
void solve() {
int n;
string s;
cin >> n >> s;
unordered_map<char, int> mp;
for (int i = 0; i < n; ++i) {
++mp[s[i]];
if (mp[s[i]] == 3) return cout << i + 1 << endl, void();
}
cout << -1 << endl;
}C 小月的书架
知识点：哈希表、计数、逆向扫描
固定位置 $i$，只需比较 $a_i$ 在它左侧和右侧的出现次数。预先统计每个编号的总出现次数，然后从右向左枚举：
- 先把当前位置从总计数中删去，此时该编号在计数表中的数量就是左侧数量；
- 另一个计数表记录已经扫过的部分，也就是右侧数量；
- 两者相等时，把位置 $i$ 加入答案。
时间复杂度平均为 $\mathcal{O}(n)$。
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
unordered_map<int, int> mp;
for (int i = 1; i <= n; ++i) cin >> a[i], mp[a[i]]++;
unordered_map<int, int> mp2;
int ans = 0;
for (int i = n; i >= 1; --i) {
mp[a[i]]--;
if (mp[a[i]] == mp2[a[i]]) ans += i;
mp2[a[i]]++;
}
cout << ans << endl;
}D 小月的相同数对
知识点：双指针、滑动窗口、计数
设当前窗口为 $[l,r]$，并记其中相同数对的数量为
$$s=\sum_x\binom{\operatorname{cnt}_x}{2}。$$
右端点加入一个值 $x$ 时，新产生的数对恰好是窗口中原有的 $x$ 的数量，因此令 $s$ 增加 $\operatorname{cnt}_x$。当 $s\ge k$ 时不断移动左端点，并在每次移动前用当前长度更新答案。若被移出的值出现了 $t$ 次，它参与的数对正好有 $t-1$ 个，所以令 $s$ 减去 $t-1$。
左右端点都只向右移动，故每个位置至多进入、离开窗口一次。
时间复杂度 $\mathcal{O}(n)$。
constexpr int inf = 1e9 + 7;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &v : a) cin >> v;
int s = 0, l = 0, ans = inf;
vector<int> cnt(n + 1);
for (int r = 0; r < n; ++r) {
s += cnt[a[r]];
++cnt[a[r]];
while (l <= r && s >= k) {
ans = min(ans, r - l + 1);
s -= cnt[a[l]] - 1;
--cnt[a[l]];
++l;
}
}
cout << (ans == inf ? -1 : ans) << endl;
}E 小月的相邻数组
知识点：差分变形、树状数组、单点修改区间查询
将条件移项：
$$a_i-a_{i-1}<a_{i+1}-a_i \iff a_{i-1}+a_{i+1}>2a_i。$$
定义 $b_i$ 表示位置 $i$ 是否满足该条件，仅需维护 $2\le i\le n-1$ 的位置。修改 $a_p$ 只会影响 $b_{p-1}$、$b_p$、$b_{p+1}$，逐个重算即可。询问 $l<i<r$ 等价于查询 $b$ 在区间 $[l+1,r-1]$ 的和，用树状数组维护这些点值。
时间复杂度 $\mathcal{O}((n+q)\log n)$。
template <class T> struct BIT {...} // 树状数组
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i];
auto calc = [&](int i) {
return (a[i - 1] + a[i + 1] > 2 * a[i]) ? 1LL : 0LL;
};
for (int i = 2; i < n; ++i) b[i] = calc(i);
BIT<int> tr(n);
tr.build(b);
while (q--) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
a[x] = y;
for (int i = max(2LL, x - 1); i <= min(n - 1, x + 1); ++i) {
int v = calc(i);
tr.modify(i, v - b[i]);
b[i] = v;
}
} else {
cout << tr.ask(x + 1, y - 1) << endl;
}
}
}F 小月的数组
知识点：模计数、线性递推、单位根反演、生成函数
法 $1$：矩阵快速幂
令 $F_n[j]$ 表示处理完 $n$ 个位置后，当前和模 $4$ 为 $j$ 的方案数，得到递推方程组。
$$\begin{aligned}F_{n+1}[0]&=F_n[0]+F_n[1]+F_n[3],\\F_{n+1}[1]&=F_n[0]+F_n[1]+F_n[2],\\F_{n+1}[2]&=F_n[1]+F_n[2]+F_n[3],\\F_{n+1}[3]&=F_n[0]+F_n[2]+F_n[3].\end{aligned}$$
可以直接写出矩阵
$$\begin{matrix}1 & 1 & 0 & 1\\1 & 1 & 1 & 0\\0 & 1 & 1 & 1\\1 & 0 & 1 & 1\\\end{matrix}$$
则初始向量为 $v_0=(1,0,0,0)$，并有 $v_n=v_0M^n$。答案就是 $M^n$ 的第 $0$ 行第 $r$ 列。
时间复杂度 $\mathcal{O}(4^3\log n)=\mathcal{O}(\log n)$。
constexpr int mod = 998244353;
using Z = MInt<mod>;
template <class T> struct Matrix {...} // 矩阵
void solve() {
int n, r;
cin >> n >> r;
Matrix<Z> f(4, 4);
for (int i = 0; i < 4; ++i) {
f[i][i] += 1;
f[i][(i + 1) % 4] += 1;
f[i][(i + 3) % 4] += 1;
}
cout << f.ksm(n)[0][r] << endl;
}法 $2$：推式子
还是从刚刚余数 $dp$ 的方程组出发，不妨记 $A_n,B_n,C_n,D_n$ 分别为和模 $4$ 等于 $0,1,2,3$ 的方案数。
初值为 $(A_0,B_0,C_0,D_0)=(1,0,0,0)$。由递推可知 $B_n=D_n$；同时
$$A_{n+1}-C_{n+1}=A_n-C_n,$$
所以始终有 $A_n-C_n=1$。令 $S_n=A_n+C_n$，并把 $B_n$ 记作两个奇数余数各自的数量，则
$$S_{n+1}=S_n+4B_n,\qquad B_{n+1}=S_n+B_n。$$
再令 $X_n=S_n+2B_n$、$Y_n=S_n-2B_n$，便有
$$X_{n+1}=3X_n,\qquad Y_{n+1}=-Y_n,$$
且 $X_0=Y_0=1$。因此
$$S_n=\frac{3^n+(-1)^n}{2},\qquad B_n=D_n=\frac{3^n-(-1)^n}{4}。$$
结合 $A_n-C_n=1$，最终得到
$$\begin{aligned}f_{n,0}&=\frac{3^n+(-1)^n+2}{4},\\f_{n,1}&=\frac{3^n-(-1)^n}{4},\\f_{n,2}&=\frac{3^n+(-1)^n-2}{4},\\f_{n,3}&=\frac{3^n-(-1)^n}{4}.\end{aligned}$$
时间复杂度 $\mathcal{O}(\log n)$。
constexpr int mod = 998244353;
using Z = MInt<mod>;
void solve() {
int n, r;
cin >> n >> r;
Z p = Z(3).pow(n);
Z e = (n & 1) ? Z(-1) : Z(1);
array<Z, 4> ans = {
(p + e + Z(2)) / Z(4),
(p - e) / Z(4),
(p + e - Z(2)) / Z(4),
(p - e) / Z(4)
};
cout << ans[r] << endl;
}法 $3$：单位根反演
令 $\omega=\mathrm{i}$ 为 $4$ 次单位根。单位根筛选公式把总和模 $4$ 为 $r$ 的项筛出：
$$f_{n,r}=\frac14\sum_{j=0}^{3}\omega^{-rj}(1+\omega^j+\omega^{3j})^n。$$
$4$ 个代入点的基函数值非常简单：
$$1+1+1=3,\qquad 1-1-1=-1,\qquad 1+\omega+\omega^3=1,$$
其中最后一个等式对 $\omega$ 和 $\omega^3$ 都成立。因此 $j=0$ 贡献 $3^n$，$j=2$ 贡献 $(-1)^{n+r}$，而 $j=1,3$ 的合计贡献在 $r=0,1,2,3$ 时分别为 $2,0,-2,0$。于是
$$f_{n,r}=\frac{3^n+(-1)^{n+r}+2\cos(\pi r/2)}{4},$$
实际计算时只需按 $r$ 的奇偶性及是否为 $0$、$2$ 分类，不需要进行复数运算。
时间复杂度 $\mathcal{O}(\log n)$。
constexpr int mod = 998244353;
using Z = MInt<mod>;
void solve() {
int n, r;
cin >> n >> r;
Z e = (n & 1) ? Z(-1) : Z(1);
Z ans = Z(3).pow(n);
if (r & 1) ans -= e;
else ans += e;
if (r == 0) ans += 2;
if (r == 2) ans -= 2;
cout << ans / Z(4) << endl;
}法 $4$：生成函数
把每个元素的取值看成 $1$ 次幂次贡献，单个位置的生成函数为 $1+x+x^3$，因此长度为 $n$ 的所有数组对应
$$F_n(x)=(1+x+x^3)^n。$$
我们只关心指数模 $4$ 的余数，所以在商环 $\mathbb{Z}[x]/(x^4-1)$ 中计算即可：
$$F_n(x)\equiv\sum_{r=0}^{3}f_{n,r}x^r\pmod{x^4-1}。$$
于是多项式乘法就是循环卷积：$x^i\cdot x^j$ 的指数折回 $(i+j)\bmod 4$。对基多项式 $1+x+x^3$ 做二进制快速幂，最终向量的第 $r$ 项即为答案。
每次循环卷积只需处理 $4^2$ 对系数。
时间复杂度 $\mathcal{O}(4^2\log n)=\mathcal{O}(\log n)$。
constexpr int mod = 998244353;
using Z = MInt<mod>;
void solve() {
int n, r;
cin >> n >> r;
using V = array<Z, 4>;
auto mul = [](const V &a, const V &b) {
V c{};
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
c[(i + j) % 4] += a[i] * b[j];
}
}
return c;
};
V ans{1, 0, 0, 0}, base{1, 1, 0, 1};
while (n) {
if (n & 1) ans = mul(ans, base);
base = mul(base, base);
n >>= 1;
}
cout << ans[r] << endl;
}约定
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii array<int, 2>
#define endl "\n"
void solve() {}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(20);
int t = 1;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}使用到的算法模板见 $\texttt{github}$ 仓库 林月的XCPC模板库