A - No Majority
简要题意
一个串 \(s\) 是好的当且仅当 \(s\) 的所有字串中没有众数。现在给定包含问号和小写拉丁字母的串 \(s\) ，问将问号替换为小写拉丁字母可以得到好串的数量，取模 \(998244353\)。
数据范围 \(|s|\le 5000\) 。
题解
显然我们只需要考虑长度为 \(3\) 的子串，因为如果一个长度 \(>3\) 的子串有众数，那么其中肯定有一个长度为 \(3\) 的子串有众数。设 \(f_{i,j}\) 表示考虑到了 \(i\) ， \(j\) 是一个 \(26\) 进制下的 \(3\) 位数，记录 \(i-2,i-1,i\) 这三个位置填了什么字母，转移显然。
B - Unique XOR Path
简要题意
给定一个 \(n\) 行 \(m\) 列的矩阵，你需要往矩阵里填 \(0\sim 2^k-1\) 中的数，使得矩阵满足如下限制条件：
- 从左上角开始只能往右或下走到右下角的一条路径是好的，当且仅当路径上的数的异或和为 \(0\) 。
- 在所有路径中，仅有给定的一条路径是好的。
请判断是否有一种填数方案使得矩阵满足条件。
题解
手玩几组数据：
\(S=RRDRDDRD\) ：
1 | 0001. |
\(S=RRRDDDRD\) ：
1 | 0000. |
发现我们需要的数的数量与拐角数量有关，更具体的，需要的 \(k=\min\{\) 下拐角数量，上拐角数量 \(\}\) ，而实际上这个结论也是对的，就可以做了。
C - Large Heap
简要题意
对于一个长度为 \(2^N-1\) 的排列 \(P\) ，我们称其为 \(\text{heaplike}\) 当且仅当满足这个排列以下条件：
- \(P_i<P_{2i}(1\le i\le2^{N-1}-1)\)
- \(P_i<P_{2i+1}(1\le i\le2^{N-1}-1)\)
给定 \(A\) 和 \(B\) ，令 \(U=2^A\) ， \(V=2^{B+1}-1\) 。
在模 \(998244353\) 意义下求在所有 \(\text{heaplike}\) 排列中等概率随机到一个满足 \(P_U<P_V\) 的排列概率。
题解
考虑一个 \(\text{heaplike}\) 排列可以如何生成，考虑从 \(1\sim2^N-1\) 依次取出数字所在的位置构成一个对 \(\text{heaplike}\) 排列的 \(\text{BFS}\) 序列， \(P_U<P_V\) 实际上就是 \(U\) 在 \(\text{BFS}\) 序列中出现的位置要比 \(V\) 早。
我们还发现 \(U\) 和 \(V\) 一个在最左边的链上，一个在最右边的链上，这就启示我们设计 \(\text{DP}\) 状态为 \(f_{i,j}\) 表示最左边链上第 \(i\) 位和最右边链上第 \(j\) 位已经出现在 \(BFS\) 序列中，但是 \(i+1\) 位和 \(j+1\) 位还没有出现在 \(BFS\) 序列中的概率。考虑如何转移，令 \(p_{i,j}\) 表示 \(i+1\) 位比 \(j+1\) 位早出现的概率，那么显然有转移：
\[ \begin{aligned} pf_{i,j}&\longrightarrow f_{i+1,j}\\ (1-p)f_{i,j}&\longrightarrow f_{i,j+1} \end{aligned} \]
考虑 \(p\) 是什么，我们发现这等价于有两个集合 \(S\) 和 \(T\) ，令 \(U=S\bigcup T\) ，对于 \(U\) 中的所有数生成一个随机排列，我们关心的是 \(U\) 中第一个数是属于 \(S\) 还是属于 \(T\) 的，如果属于 \(S\) 则 \(S\) 在 \(T\) 的前面，反之亦然。那么就有 \(S\) 在 \(T\) 的前面的概率就是 \(p=\dfrac{|S|}{|S|+|T|}\) ，在本题中即为 \(p=\dfrac{sz_{i+1}}{sz_{i+1}+sz_{j+1}}\) ，其中 \(sz_i\) 表示以 \(i\) 为根的子树大小。
考虑如何统计答案，根据状态意义有 \(ans=\sum\limits_{i=0}^{B-1}pf_{A-1,i}\) ，即可求得答案。
Besize：谁会 \(O(N\log^2N)\) 做法啊，求教教，盲猜多项式。
D - Same Descent Set
简要题意
在模 \(998244353\) 意义下找到 \(1\sim n\) 的排列对 \((P,Q)\) 的数量，满足以下要求：
- \(P\) 和 \(Q\) 在任意位置同单调性。
题解
通过样例查oeis可知就是A060350(n)，然后就做完了。
考虑钦定某些位置 \(P_i<P_{i+1}\) ，某些位置 \(P_i>P_{i+1}\) ，记 \(P_i<P_{i+1}\) 的位置集合为 \(S\) ，记符合条件的排列数为 \(cnt(S)\) ，那么这种情况的贡献就是 \(cnt(S)^2\) 。
考虑容斥求 \(cnt(S)\) ，记 \(f(x)\) 为 \(\forall i\notin x\) ，满足 \(P_i<P_{i+1}\) 的排列数量，那么有 \(cnt(S)=\sum\limits_{x\in S}f(x)(-1)^{|x|}\) ，那么现在的答案就是 \(ans=\sum\limits_S\sum\limits_{a,b\subset S}f(a)f(b)(-1)^{|a|+|b|}\) 。
考虑交换求和顺序，则有:
\[ \begin{aligned} ans&=\sum_{a,b}f(a)f(b)(-1)^{|a|+|b|}\cdot2^{n-1-|a|-|b|+|a\cap b|}\\ &=2^{n-1}\sum_{a,b}\frac{f(a)}{(-2)^{|a|}}\cdot\frac{f(b)}{(-2)^{|b|}}\cdot2^{|a\cap b|} \end{aligned} \]
我们发现除了 \(2^{|a\cap b|}\) 之外都挺好做的，考虑如何处理 \(2^{|a\cap b|}\) ，发现有式子 \(2^{|a\cap b|}=\sum\limits_{c\subset a\cap b}1\) ，带入得到：
\[ \begin{aligned} ans&=2^{n-1}\sum_{a,b}\frac{f(a)}{(-2)^{|a|}}\cdot\frac{f(b)}{(-2)^{|b|}}\cdot\sum_{c\subset a\cap b}1\\ &=2^{n-1}\sum_c\left(\sum_a\frac{f(a)}{(-2)^{|a|}}\right)^2 \end{aligned} \]
考虑这个东西实质在做什么，显然有 \(f(a)=\dfrac{n!}{d_1!\cdot d_2!\cdots d_k!}\) ，其中 \(d_i\) 为划分 \(a\) 中每段的长度，总共有 \(k\) 段，带入上面的表达式有：
\[ \begin{aligned} ans&=2^{n-1}\sum_c\left(\sum_a\frac{1}{(-2)^{|a|}}\cdot\frac{n!}{d_1!\cdot d_2!\cdots d_k!}\right)^2\\ &=2^{n-1}n!^2\sum_c\left(\sum_a\frac{1}{(-2)^{|a|}}\cdot\frac{1}{d_1!\cdot d_2!\cdots d_k!}\right)^2 \end{aligned} \]
那么我们实际上在做的就是，将 \(1\sim n\) 划分为若干段，并计算所有划分产生的贡献，想清楚了这个式子的本质之后，启发我们用 \(\text{dp}\) 解决这个问题。
设状态 \(f_i\) 表示已经划分了 \(1\sim i\) 且 \(i\) 为最后一段的末尾的总方案数，需要注意的是这里的划分是对 \(c\) 做的，为了计算 \(a,b\) 的贡献，我们还需要一个 \(\text{dp}\) ，设 \(g_i\) 表示划分一段长度为 \(i\) 的段所产生的贡献，我们可以得到如下递推式：
\[ \begin{aligned} f_i&=\sum_{j<i}f_j\cdot\left(\frac{g_{i-j}}{-2}\right)^2\\ g_i&=\sum_{j<i}g_j\cdot\frac{1}{-2\cdot(i-j)!} \end{aligned} \]
那么这个问题就转化为了一个经典的分治 \(\text{NTT}\) 处理的递推问题，时间复杂度为 \(O(N\log^2N)\) 。或者还有经典多项式求逆做法，时间复杂度为 \(O(N\log N)\) 。详见 \(\text{Luogu P4721}\) 。
Main Code
1 | int n; cin >> n; |
E - Number of Cycles
TBD...
F - Spanning Trees of Interval Graph
TBD...