对于每一轮对局的 $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$。 （更多…）
$T \leq 1000$ 组数据。给定 $n, a, b, c\in [0, 10^9], k_1,k_2\in [0, 10], k_1+k_2\leq 10$，求取
$$
\sum_{x=0}^{n}x^{k_1}\left\lfloor\frac{ax+b}{c}\right\rfloor^{k_2}
$$
当 $k_1=0,k_2=1$ 时，是为一般类欧几里得算法的模板。上述链接亦给出了 $k_1=0,k_2=2; k_1=1,k_2=1$ 时的解法。
当 $k_2=0$ 时，该式退化为 $\sum_{x=0}^{n}x^{k_1}$，即 $k_1$ 次的等幂求和。有一个模糊的结论：
设 $n$ 为正整数。则$k$ 次的等幂求和，$\sum_{x=0}^{n}x^k$，是一个关于 $n$ 的 $k+1$ 次多项式。
该结论来源于 zyw 学姐多项式专题所选题目 BZOJ 3453 – tyvj 1858 XLkxc。之所以说模糊，是因为该多项式的系数是已知的。不过我们仍然可以暴力计算 $k+2$ 个点以插值。
再观察 OI-Wiki 上对于 $k_1+k_2\leq 2$ 时的解法。在求取
$$h(n,a,b,c)=\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2$$时采取了如下转化：
$$\begin{aligned}
x^2&=2\times \frac{x(x+1)}{2}-x\\
&=2\left(\sum_{y=1}^{x}y\right)-x\end{aligned}
\quad\begin{aligned}
\Longrightarrow\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2=\sum_{x=0}^n2\left(\sum_{y=1}^{\left\lfloor\frac{ax+b}{c}\right\rfloor}y\right)-\left\lfloor\frac{ax+b}{c}\right\rfloor\\
\end{aligned}$$
这样一来，由于 $y$ 是一个线性算子，在 $ax+b\geq yc$ 时都有 $y$ 向总和贡献，于是我们可以应用类似于 $k_1=0,k_2=1$ 时的方法转化贡献。这个过程对 $k_2$ 作了降次。
那么，对于更高次项，有无办法采取同样的办法转化呢？是否可以设计一些转化，使得要求取的函数 $f(\cdots,k_1,k_2)$ 能够由 $f(\cdots,k_1-?,k_2-?)$ 推出呢？ （更多…）
Educational Codeforces Round 133 F – Bags with Balls
题目中存在高次项的和。则我们分别计算有 $p=1,2,\cdots,n$ 个袋子选择奇数号球时的方案。对于选择了奇数号球的袋子，每个有 $\lceil \frac{m}{2} \rceil$ 种选择；偶数的则有 $\lfloor \frac{m}{2} \rfloor$ 种。因此答案为：
$$
\sum_{p=0}^{n}p^k\dbinom{n}{p}\Big\lceil\frac{m}{2}\Big\rceil^p\Big\lfloor \frac{m}{2} \Big\rfloor^{n-p}
$$
由于 $n\leq 10^9$，这式子看起来非常棘手。但我们注意到，有 $k\leq 2000$，这提示我们或许应该转变对答案的贡献方式：从高次幂入手，找到 $\mathrm{O}(\operatorname{poly} k)$ 而非 $\mathrm{O}(n)$ 的算法。 （更多…）
有函数 $f,g$，则 $\forall n \in \mathbb{N},$
$$\begin{aligned}
f(n)=\sum\limits_{x=0}^{n}\dbinom{n}{x}g(x) &\iff g(n)=\sum\limits_{x=0}^{n}(-1)^{n-x}\dbinom{n}{x}f(x) && (1)\\
f(n)=\sum_{x=0}^{n}(-1)^x\dbinom{n}{x}g(x) &\iff g(n)=\sum\limits_{x=0}^{n}(-1)^x\dbinom{n}{x}f(x) && (2)\\
f(n)=\sum_{x=n}^{+\infty}\dbinom{x}{n}g(x) &\iff g(n)=\sum_{x=n}^{+\infty}(-1)^{x-n}\dbinom{x}{n}f(x) && (3)
\end{aligned}$$
（6月22日追记：式 $(1),(3)$ 在OI中是最常用的。尤其是 $(3)$，阐述了在计数类问题中钦定 $x$ 个元素满足某种属性（$f(x)$），其他元素任意，与恰好有 $x$ 个元素满足某种属性（$g(x)$）之间的对应关系。）
或许是人品不错，最近两天接连刷到三道排列组合相关的题。在此作简单整理。
题意参见原题面。
很自然地想到，对于一个排列$P = (p_1, p_2, \dots, p_n)$，有$n$条$i \rightarrow p_i$的连边。因为排列中正整数$1, 2, \dots, n$恰好出现仅有一次，所以等价于每个点有且仅有一条出边、一条入边的图。容易发现这个图由若干个有向环构成（包括自环——即$p_i = i$的情况）。例如排列$P = (1, 3, 4, 2)$代表由$1 \rightarrow 1$和$2 \rightarrow 3 \rightarrow 4 \rightarrow 2$两个环组成的图。