T1

100%

直接比较大小然后输出即可。

时间复杂度 $O(1)$ 。

T2

100%

由于不同位置的 ? 可以替换成不同的字母，因此只需要对每个位置判断是否能够相等即可。

遍历每个位置 $i$，如果 $S[i]$ 和 $T[i]$ 都是小写字母且不相同，那么一定无法相同；否则若有至少一个 ? 或已经相同，则该位置可以相同。

时间复杂度 $O(n)$ 。

T3

100%

由于只需要在所有操作结束后输出每个格子的印章状态，因此我们可以通过一个数组 $d$ （初始为0）来记录每个格子的印章状态被修改的次数，当机器人处于工作状态 1 并走到 $i$ 位置时，$d[i]=d[i]+1$，最后 $d[i]$ 为奇数表示该位置有印章，偶数表示没有。

接下来只需要模拟每个操作：移动机器人并更新 $d$ 数组；改变方向；改变工作状态。

需要注意的是更新 $d$ 数组时不能暴力枚举每个位置进行 $+1$，否则是 $O(n*Q)$ 的时间复杂度。

由于我们需要做的是区间 $+1$ ，以及只需要在最后进行单点查询，因此可以通过差分数组来实现：对于区间 $[l,r]$ 加1，在差分数组 $diff[l]+1$，$diff[r+1]-1$，最后做一遍前缀和即可得到 $d$ 数组。

时间复杂度 $O(n+Q)$。

T4

100%

首先一个连续子串，通过至多 $k$ 次操作，使得子串中的所有字符相同，最终子串的字符一定是在原本子串中出现次数最多的字符，这样可以使用更少的操作次数。因此“好子串”的条件等价于：

$$len-maxcnt \leq k$$

其中 $len$ 为子串长度，$maxcnt$ 为出现次数最多的字符的次数。

暴力枚举所有子串需要 $o(n^2)$ 的时间复杂度，显然不行，考虑如何快速计算答案。

假设当前有一个“好子串”，当我们向右增加一个字符时，$len-maxcnt$ 的值要么不变（增加的是出现最多的字符），要么增加1（增加的不是出现最多的字符）。

因此对于固定的左端点 $l$，可以找到一个最大的满足条件的右端点 $r$，使得 $[l,r_0] (l \leq r_0 \leq r)$ 都是好子串，并且随着 $l$ 右移，$r$ 也是单调向右移动的。对于每个 $l$ 所对应的 $r$，对答案的贡献为 $r - l + 1$。

于是便可以利用双指针（滑动窗口）的方式，维护当前子串每个字符出现次数，即可快速统计答案。

时间复杂度为 $O(n)$。

T5

100%

我们需要统计树上所有简单路径中，点权和为偶数且 $\geq 2$ 的路径数量。这是一个经典的树形 DP 问题，考虑每条路径在其最高点（LCA）处统计。

对于结点 $u$，定义状态：

• $dp[u][0]$ 表示从 $u$ 出发，向下的所有路径（包括 $u$ 自身）中，点权和为 0 的路径条数；
• $dp[u][1]$ 表示从 $u$ 出发，向下的所有路径中，点权和为奇数的路径条数；
• $dp[u][2]$ 表示从 $u$ 出发，向下的所有路径中，点权和为偶数（不包含 0）的路径条数；

转移时枚举 $u$ 的每个儿子 $v$，然后根据 $c_u$ 分类讨论：

如果 $c_u=1$：

• $dp[u][1]+=dp[v][0]+dp[v][2]$
• $dp[u][2]+=dp[v][1]$

如果 $c_u=0$：

• $dp[u][0]+=dp[v][0]$
• $dp[u][1]+=dp[v][1]$
• $dp[u][2]+=dp[v][2]$

统计以 $u$ 为 LCA 的“好路径”可以在枚举 $v$ 的过程中计算：

在当前已合并的部分 dp[u] 与子树 v d的 $dp[v]$ 中各选一条路径，进行拼接。要统计点权和为偶数且不为 0 的方案数，有四种情况：

• $dp[v][2] \times dp[u][0]$
• $dp[v][2] \times dp[u][2]$
• $dp[v][1] \times dp[u][1]$
• $dp[v][0] \times dp[u][2]$

累加这四项到答案中，再对 $v$ 进行转移即可。

时间复杂度 $O(n)$。

另外也可以先求出所有点权和为偶数的路径数，再减去点权和为 0 的路径数，这样 dp 只需要两个状态，但需要额外计算点权和为 0 的路径数。

T6

100%

由于 $f_n$ 始终是 $a!$ 和 $b!$ 的乘积，因此可以写成：

$$f_n=(a!)^{x_n} \cdot (b!)^{y_n}$$

由递推式 $f_n=f_{n-1} f_{n-2}$ 得：

$$x_n=x_{n-1}+x_{n-2} \;,\; y_n=y_{n-1}+y_{n-2}$$

因此 $x_n$ 和 $y_n$ 都是斐波那契数列，由于 $n \leq 10^{14}$，因此需要利用矩阵快速幂计算，时间复杂度 $O(\log n)$。

接下来要求 $f_n$ 的因子个数，需要将 $f_n$ 分解质因子：

$$f_n=\prod_p p^{c_p}$$

则正因子个数为：

$$d(f_n)=\prod_p (c_p+1)$$

即我们需要知道 $f_n$ 的每个质因子的指数。

对于 $n!$，质数 $p$ 的指数为：

$$v_p(m!)=\sum_{k=1}^{\infty} \left \lfloor \frac{m}{p^{k}} \right \rfloor $$

因此需要先筛出 $max(a,b)$ 范围内的所有质数，即可快速计算每个质数的指数，然后：

$$d(f_n)=\prod_p (v_p(a!) \cdot x_n + v_p(b!) \cdot y_n +1) \;\bmod 998244353 $$

根据模运算的分配律，可以对 $x_n$ 和 $y_n$ 取模来进行计算，也就是将矩阵快速幂中的所有运算直接对 998244353 取模（不是对 $a!$ 取模）。

时间复杂度 $O(N)$ （线性筛）。