2025--炼石计划-- 10 月 06 日 --NOIP 模拟赛 #10【订正】 - 比赛 - 梦熊联盟 (mna.wang)
复盘
T1 计数题，感觉不难。用样例模拟了一下，找到一个较优的去重方式。然后过了样例。此时 8:10。
T2 好像又是矩阵加速。想正解。
想不出来，只能做到 \(\mathcal O(n^6 \log k)\) 的复杂度。加上一些别的 DP 能做到 50。
先放弃。此时 11:00 了，后两题还没想，先往后做。
T3, T4 各有显然 15 分。先打暴力。
T3, T4 各有不是特别显然的 5 分。写。
差不多就结束了。挂了 T3 的 5 分，以及 T4 暴力的 -10（？）分，\(100+50+10+35\)。
补题 \(100+100+10+35\)。
总结
好的：
- 矩阵加速仍然没写挂。
不足：
- 越简单的部分分越不仔细。
- 后两题开始时间有点晚，虽然这场没出问题但是也很危险。
知识点
- T1：前缀和；
- T2：矩阵加速，DP；
题解
A. 字符串
显然 \(\tilde s[i, j]\) 是由一个前缀和一个后缀组成的。
对于多个相同的 \(\tilde s[i_0, j_0], \tilde s[i_1,j_1]\dots\) 而言，我们不妨将贡献只在前缀最短时计算，即 \(i\) 最小时计算贡献。
考虑枚举 \(i, j\)。我们要判断 \(\tilde s[i+1,j-1]\) 是否满足上面的条件（即串本身不变的情况下 \(i\) 最小）。考虑什么时候不满足，即存在一个正整数 \(k\) 使得：
\[s[1,i]+s[j,n] = s[1,i+k] + s[j+k,n] \]这样又可以写成：
\[s[1,i]+s[j,j+k-1]+s[j+k,n] = s[1,i]+s[i + 1, i + k] + s[j + k, n] \]消去律（？）可以变成：
\[s[j,j+k-1]=s[i+1,i+k] \]也就是说，如果 \(\tilde s[i+1,j-1]\) 应该贡献给答案，那么必须不能存在一个正整数 \(k\) 使得从 \(i+1,j\) 后面分别取 \(k\) 个字符后得到的字符串完全相同。
不难发现 \(k = 1\) 完全可以决定这个命题的真假。所以 \(\tilde s[i+1,j-1]\) 应该贡献到答案中，当且仅当 \(s_{i+1} \ne s_j\)。
于是问题变成了求字符串中有多少对字符不相同。
B. 别回头
设 \(f(t, i)\) 表示 \(t\) 秒时恰好到达 \(i\)，且没有连续经过同一条边的方案数。\(g(t, i, j)\) 表示 \(t\) 秒时恰好到达 \(j\)，且没有连续经过同一条边，且最后一条经过的边是 \(i \to j\) 的方案数。显然有：
\[f(t, i) = \sum_{j \to i} g(t,j,i) \]考虑转移：
\[f(t, i) = \sum_{j \to i}\Big(f(t-1,j) - g(t-1,i,j)\Big) \\ g(t, i, j) = \sum_{k \to i}g(t-1,k,i) - g(t-1,j,i) \]代一下：
\[g(t, i, j) = f(t-1,i) - g(t-1,j,i) \]再代一下：
\[\begin{aligned} f(t, i) &= \sum_{j \to i}\Big(f(t-1,j) - f(t-2,i) + g(t-2,j,i)\Big) \\ &= \sum_{j\to i} f(t-1,j) - \text{degree}(i) \times f(t-2,i) + \sum_{j\to i} g(t-2,j,i) \\ &= \sum_{j\to i} f(t-1,j) - \text{degree}(i) \times f(t-2,i) + f(t-2,i) \\ &= \sum_{j\to i} f(t-1,j) - (\text{degree}(i)-1) \times f(t-2,i) \end{aligned} \]其中 \(\text{degree}(i)\) 表示 \(i\) 的度数。
此时整个式子和 \(g\) 无关了。剩下的就是矩阵加速的问题了。这是单次询问。
多组询问的处理方法见 有趣矩阵技巧 - 洛谷专栏。
标签：10,NOIP,degree,10.9,Big,sum,text,tilde From： https://www.cnblogs.com/2huk/p/18454828