对于每一轮对局的 $m!$ 种排列，对于编号为 $a$ 的牌，恒有 $(m-1)!$ 种是以牌 $a$ 为首的。因此一轮可以归为 $m$ 种情况，首张为王牌的概率为 $\frac{1}{m}$。
这是某场模拟考试给出的部分分：
$$
\begin{array}{cccc}
\text{Subtask}&\text{Constraints}&\text{Points}&\text{Dependencies}\\ \hline
1&n,m,k\leq 5&2&\\
2&k=1&2&\\
3&k\leq 5000&10&1,2\\
4&m\leq 100&10&1\\
5&n\leq k&5&\\
6&k\leq 10^5&10&1,2,3\\
7&k\leq 5\times 10^6&20&1,2,3,6\\
8&&41&1\sim 7
\end{array}
$$ （更多…）
AGC058D – Yet Another ABC String
将 $\mathtt{A,B,C}$ 换成 $0,1,2$。记 $a,b,c$ 是题面中 $\mathtt{A,B,C}$ 的数量，$n=a+b+c$。我们称位置 $i$ 不合法，当且仅当 $S_{i-2}+2\equiv S_{i-1}+1\equiv S_i\pmod 3$。将其视为两条边 $(i-2,i-1),(i-1,i)$，那么所有不合法的位置造成的连边将会形成若干条链。
考虑容斥。直接钦定指定数量的位置不合法，其方案是难以计算的。又因为容斥系数是 $(-1)^c$，$c$ 为钦定的非法位置数量，那么将整个串分成若干个部分分别计算方案，带上容斥系数相乘后累加，结果不变。故而尝试从上文的链入手：易得对于固定长度的一条链，能够连成它的非法位置集合不变。设 $f(l,0)$ 表示“大小为偶数，且能够连成长度恰为 $l$ 的链”的非法位置集合数量；$f(l,1)$ 则是大小为奇数。染色方案与位置集合方案是独立的；则设整个串按顺序被分成了链 $(l_1,l_2,\cdots,l_s)$（此处的“链”长度均不小于 $3$），答案即为
$$\sum_{(l_1,\cdots,l_s)}\operatorname{染色方案数}\left((l_1,\cdots,l_s)\right)\prod_{i=1}^s\left((-1)f(l_i,1)+f(l_i,0)\right)$$ （更多…）
NOIP+？准省选难度？已经到了能力的边缘么？
但有点奇怪的是，这三道题的思考方向全部正确，T1 甚至只差临门一脚了；可惜部分分给得不那么让人舒服。
另外，这种“为了卡常而卡常”的时间限制着实令人不适；尤其是当 CWOI 的评测机本身配置落后的情况下。不过这也反过来使得我重新开始关注更底层的常数优化。
这道破题拖了我整整一天。
题目所给限制可以表述为，$a$ 和 $b$ 均为单调不降的序列，长度相等（记为 $k$），且 $a_1=0,a_k=n,b_1=0,b_k=m,\nexists i\in[2,k],a_i=a_{i-1}\land b_i=b_{i-1}$。
考虑差分序列 ${a_i}’=a_i-a_{i-1}\quad(i\in[2,k])$，${b_i}’$ 同理，它与原序列形成双射。于是不存在 ${a_i}’={b_i}’=0$ 的差分序列合法。考虑 $\sum_{i=2}^{k}{a_i}’=n$，也就是和为 $n$ 的 $k-1$ 元线性方程组的一组非负整数解；$b’$ 同理。容易计算“钦定至少有 $c$ 个位置不合法”的方案数——利用容斥原理即可得到长为 $k$ 的合法序列对个数为
$$\sum_{c=0}^{k-2}\binom{k-1}{c}\binom{n+(k-1)-1-c}{(k-1)-1-c}\binom{m+(k-1)-1-c}{(k-1)-1-c}(-1)^c$$ 答案累加上式结果 $\times k$。 （更多…）