10.9（NOIP 模拟赛 #10）

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\) 无关了。剩下的就是矩阵加速的问题了。这是单次询问。

多组询问的处理方法见 有趣矩阵技巧 - 洛谷专栏。