2025.10.3 测试

A.

思考如何匹配子序列，肯定是贪心的能扩展就扩展，将这个过程改写成 DP 。

设 \(f[i, j]\) 表示 \(S\) 匹配了 \(i\) 位，\(T\) 匹配了 \(j\) 位的方案数。

枚举下一位匹配位置得到转移式：

\(f[i, j]=\sum_{k<j}f[i-1,k]\times 25^{j-k-1}\) 。

拆式子得到

\[f[i,j]\times 25^{-j}=\frac{1}{25}\sum_{k<j}f[i-1,k]\times 25^{-k}\\ g[i,j] = \frac{1}{25}\sum_{k<j}g[i-1, k] \]

改写成生成函数的形式

\[G(i)=\frac{\frac{1}{25}x}{1-x}\times G(i-1)\\ G(0)=1 \]

则最终

\[\begin{align*} ans&=\sum_{i=n}^{n+k} 25^i 26^{n+k-i}[x^i](\frac{\frac{1}{25}x}{1-x})^n\\ &=\sum_{i=n}^{n+k}25^{i-n}26^{n+k-i}[x^{i-n}](\frac{1}{1-x})^n\\ &=\sum_{i=0}^{k}25^i26^{k-i}[x^i](\frac{1}{1-x})^n\\ &=\sum_{i=0}^{k}25^i26^{k-i}{i+n-1\choose n-1}\\ \end{align*} \]

直接计算即可。

教师

考虑 \(k=1\) 的部分分，扫描右端点，考虑哪些位置可以作为合法的左端点。

对于一个数字 \(a\) ，依次出现在 \(p_1, p_2, p_3, \cdots p_t\) ，则 \((p_{t-1},p_t]\) 是合法的，记作 \(\mathcal S_a\) 。

所有合法的左端点位置 \(\mathcal T=\bigcup S_a\) 。

矩形面积并模板。

稍稍扩展一下这个做法，记 \(\mathcal T_i\) 为使得 \(k=i\) 合法的左端点集合。

则要求 \(\mathcal Q=\bigcap T_i\) ，容斥一下得到 \(k=3\) 时的式子：

\[\left| \mathcal Q \right|=\left| \mathcal T_1 \right|+\left| \mathcal T_2 \right|+\left| \mathcal T_3 \right|-\left| \mathcal T_1\cup\mathcal T_2 \right|-\left| \mathcal T_1\cup\mathcal T_3 \right|-\left| \mathcal T_2\cup\mathcal T_3 \right|+\left| \mathcal T_1\cup\mathcal T_2\cup\mathcal T_3 \right| \]

做 \(2^k\) 遍矩形面积并即可。

Link

崩坏3？非酋之战！

注意到只有减速，叠 buff ，以及大招是有用的。

同时发现，大招一定是最后放的，然后前两者直接 \(\mathcal O(n^2)\) DP 即可。

Link
\(\mathcal O(n)\) 做法参考 Link 。

第三心脏

两侧平方得 \(a^2+b^2+c^2+d^2=(a\oplus b\oplus c\oplus d)^2>d^2\) ，则 \(a\oplus b\oplus c\oplus d>d\) 。

不妨设 \(a\oplus b\oplus c\oplus d=d+x\) ，且 \(d\vee x=0\) 。（\(\vee\) 表示按位或）

为了方便不妨设 \(x=1\) ，则 \(a\oplus b\oplus c=1 , d\equiv 0\pmod 2\) 。

且 \(a^2+b^2+c^2+d^2=(d+1)^2 \Rightarrow d=\frac{a^2+b^2+c^2-1}{2}\) 。

设 \(a\) 的二进制最高位为 $ p$ 。

如果 \(a\equiv 0\pmod 2\) ，则令 \(b=a+2^p, c=2^p+2^{p+1}+1\) 。

如果 \(a\equiv 1\pmod 2\) ，则令 \(b=a+2^p-1, c=2^p+2^{p+1}\) 。

容易验证 \(d\equiv 0 \pmod 2\) 。

Link