洛谷

魔改 KMP 大概是不行的，卷积在这里出现的很妙。 卷积处理匹配 定义匹配函数 $$ d(x,y) = [x = y] $$ 给定文本串 $B$ 和长为 $m$ 的模式串 $A$，要找出 $A$ 在 $B$ 的所有出现，可以定义 $$ f(k) = \sum_{i=0}^{m-1} d(A_{i}, B_{i-m+k}) $$ 即 $f(k) = 0$ 时有完全匹配 $A = B[k-m\ldots k-1]$。考虑让 $d$ 函数更 “数学” 一点，以更好的计算 $$ d(x,y) = (x - y)^2 $$ 再提供模式串 $A$ 的翻转 $S$，即 $A_i = S_{m-i}$，展开有 $$ \begin{aligned} f(k) &= \sum_{i=0}^{m-1}A_{i}^2 + \sum_{i=0}^{m-1}B_{i-m+k}^2 - 2\sum_{i=0}^{m-1} A_{i}B_{i-m+k}\\ &= \sum_{i=0}^{m-1}A_{i}^2 + \sum_{i=0}^{m-1}B_{i-m+k}^2 - 2\sum_{i=0}^{m-1} S_{m-i}B_{i-m+k} \end{aligned} $$...

题目大意 求杨辉三角形前 $n$ 行的偶数个数，对 $1000003$ 取模。 分析 对杨辉三角奇数打表。 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 于是递推公式...

题目大意 即求 $$ \sum_{i=1}^N \sum_{j=1}^M [\gcd(i,j) \in \mathbb{P}] $$ 分析 先转化一下 $$ \sum_{i=1}^N \sum_{j=1}^M [\gcd(i,j) \in \mathbb{P}] = \sum_{p}\sum_{i=1}^N \sum_{j=1}^M [\gcd(i,j) = p] $$ 在 P2522 中得到 $$ \sum_{i=1}^x \sum_{j=1}^y [\gcd(i,j) = k] = \sum_{t=1}^{\min(x,y)} \mu(t) \left\lfloor \frac{x}{tk} \right\rfloor \left\lfloor \frac{y}{tk} \right\rfloor $$ 代入有 $$ \sum_{p} \sum_{t=1}^{\min(x,y)} \mu(t) \left\lfloor \frac{x}{tp} \right\rfloor \left\lfloor \frac{y}{tp} \right\rfloor $$ 令 $T = tp$，$T$ 的上界应还是 $\min(x,y)$，代入有 $$ \sum_{T=1}^{\min(x,y)} \left\lfloor \frac{x}{T} \right\rfloor \left\lfloor \frac{y}{T} \right\rfloor \sum_{p \mid T} \mu\left(\frac{T}{p}\right) $$...

题目大意 设 $$ \varphi_{x+1}(m) = \varphi(\varphi_x(m)) $$ 求最小的 $x$ 使得 $\varphi_x(m) = 1$。 其中 $\varphi(m)$ 是欧拉函数。 分析 注意到仅有 $\varphi(1) = \varphi(2) = 1$，再有公式 $$ \varphi\left(\prod_{i=1}^mp_i^{q_i}\right) = \prod_{i=1}^m(p_i-1)p_i^{q_i-1} $$ 因此从唯一分解形式的角度来看，迭代一次消去了一个 $2$，也生成了一些 $2$。 考虑设 $f(n)$ 为 $\varphi(n)$ 中因子 $2$ 的个数。 设 $\gcd(a,b) = 1$，可以证明 $f(ab) = f(a) f(b)$。同时 $f(p) = f(p-1)$。 这说明 $f(x)$ 是一个积性函数，可以用 Euler 筛递推。 const ll MN = 1e5 + 10; bool notp[1000001]; int prime[200001], cnt, phi[1000001]; void sieve(int n) { phi[1] = 1; for (ll i = 2; i <= n; i++) { if (!...

题目大意 即求 $$ \sum_{i=1}^n \gcd(i,n) $$ 分析 联想到 $$ \varphi(n) = \sum_{i=1}^n [\gcd(i,n) = 1] $$ 尝试凑这个形式 $$ \begin{aligned} \sum_{i=1}^n \gcd(i,n) &= \sum_{d \mid n} d \sum_{i=1}^n [\gcd(i,n) = d] \\ &= \sum_{d \mid n} d \sum_{i=1}^{n/d} [\gcd(i,n/d) = 1] \\ &= \sum_{d \mid n} d \varphi(n/d) \end{aligned} $$ 这里其实已经可以过题了，但还可以再瞎搞一下，令 $$ nf(n) = \sum_{d \mid n} d \varphi(n/d) = n\sum_{d \mid n} \frac{\varphi(d)}{d} $$ 尝试证明 $f(n)$ 是一个积性函数。设 $\gcd(a,b) = 1$，有...

题目大意 给定 $g[1], \cdots, g[m]$，求序列 $f$。 $$ f [n] = \sum_{j = 1}^n f [n - j] g [j] = \sum_{j = 1}^n f [n - j] h [j] $$ 分析 不妨令 $g [0] = 0$，$h (x) = g (x) + h [0]$，我们要解方程 $$ f [n] = \sum_{j = 1}^n f [n - j] g [j] = \sum_{j = 1}^n f [n - j] h [j] $$ 这个形式看似卷积，但实际上它缺了一项。对 $n > 0$ 凑卷积...

题目大意 即求 $$ \sum_{i=a}^b \sum_{j=c}^d [\gcd(i,j) = k] $$ 分析 容易想到，独立出函数 $f(k)$ 使得 $$ f(k) = \sum_{i=1}^x \sum_{j=1}^y [\gcd(i,j) = k] $$ 利用 Mobius 反演化简，设 $F(d)$ $$ F(n) = \sum_{n \mid d} f(d) = \sum_{i=1}^x \sum_{j=1}^y [n \mid i][n \mid j] = \left\lfloor \frac{x}{n} \right\rfloor \left\lfloor \frac{y}{n} \right\rfloor $$ 反演化简有 $$ f(n) = \sum_{n \mid d} \mu\left(\frac{d}{n}\right)F(d) = \sum_{t=1}^{\min(x,y)} \mu(t) \left\lfloor \frac{x}{tn} \right\rfloor \left\lfloor \frac{y}{tn} \right\rfloor $$ 预处理出 $\mu(t)$ 的前缀和，剩下的就是一个二重分块了。...

题目大意 给出正整数 $n$ 和 $k$，请计算 $$ G(n, k) = \sum_{i = 1}^n k \bmod i $$ 分析 因为 $$ k \bmod i = k - i \left\lfloor \frac{k}{i} \right\rfloor $$ 因此有 $$ G(n,k) = nk - \sum_{i=1}^n i \left\lfloor \frac{k}{i} \right\rfloor $$ 后面需要整数分块。 int main() { ll n = rr(); ll k = rr(); ll sum = n * k; n = min(n, k); for (ll l = 1, r; l <= n; l = r + 1) { r = min(n, k / (k / l)); ll t = (l + r) * (r - l + 1) / 2; sum -= t * (k / l); } printf("%lld", sum); return 0; }

题目大意 对于一个区间 $[l_i,r_i]$，计算矿石在这个区间上的检验值 $y_i$： $$ y_i=\sum_{j=l_i}^{r_i}[w_j \geqslant W] \times \sum_{j=l_i}^{r_i}[w_j \geqslant W]v_j $$ 记检验结果为 $y=\sum y_i$，对于给定的 $s$，求 $|y-s|$ 的最小值。 分析 注意到 $y(w)$ 是关于 $W$ 的递减函数，对 $w$ 在 $[w_{\min},w_{\max}]$ 上进行二分。 const ll MN = 2e5 + 10; ll vv[MN], ww[MN], li[MN], ri[MN], f1[MN], f2[MN]; ll n, m, s; int main() { n = rr(), m = rr(), s = rr(); ll minw = 0x3f3f3f3f, maxw = 0; f1[0] = f2[0] = 0; for (ll i = 1; i <= n; i++) { ww[i] = rr(), vv[i] = rr(); maxw = max(ww[i], maxw); minw = min(ww[i], minw); } for (ll i = 1; i <= m; i++) { li[i] = rr(), ri[i] = rr(); } ll l = minw, r = maxw + 1; while (l < r) { int mid = (l + r) >> 1; if (sum(mid) <= s) r = mid; else l = mid + 1; } ll rst = min(sum(l - 1) - s, s - sum(l)); printf("%lld", rst); return 0; } 区间求和可以用前缀和优化。...

题目大意 对于字符串 $a,b$，若 $a$ 的末尾与 $b$ 的开头有部分字符串相同，则其可以拼接起来。例如 at + tact = atact。 给定词典和初始字母，每个单词最多出现两次，求最大拼接长度。 分析 我是没想出来，经题解提示了拼接函数才写出来的。 设 $mt(x,y)$ 为第 $x$ 和 $y$ 个单词拼接后的最小重合长度，其可简单的通过匹配得到。 char s[30][100]; ll len[30]; ll mt[30][30]; void init(int x, int y) { ll ml = min(len[x], len[y]) - 1; for (ll i = 1; i <= ml; i++) { int flag = 1; for (ll j = 0; j <= i - 1; j++) { if (s[x][len[x] + j - i] !...