计数
加法原理和乘法原理
P7140 [THUPC2021 初赛] 区间矩阵乘法
给定序列 \(\{a_n\}\)，\(m\) 次询问，每次给定 \(d,p_1,p_2\)，求：
\[\sum_{i=0}^{d-1} \sum_{j=0}^{d-1} \sum_{k=0}^{d-1} a_{p_1+di+j} a_{p_2+dj+k}. \]
令 \(\{s_n\}\) 为 \(a\) 的前缀和，\(f_d(p)=\sum_{i=0}^{d-1} a_{p+di}\)。
\[\begin{aligned} \text{原式} &=\sum_{i=0}^{d-1}\sum_{j=0}^{d-1} a_{p_1+di+j}(s_{p_2+dj+d-1}-s_{p_2+dj-1})\\ &=\sum_{j=0}^{d-1} (s_{p_2+dj+d-1}-s_{p_2+dj-1}) \sum_{i=0}^{d-1} a_{p_1+j+di}\\ &=\sum_{j=0}^{d-1} (s_{p_2+dj+d-1}-s_{p_2+dj-1}) f_d(p_1+j) \end{aligned} \]因为保证式子中的下标不会超过范围，所以 \(d\le \sqrt{n}\)。显然对于固定的 \(d\)，\(f_d(*)\) 可以 \(\mathcal{O}(n)\) 预处理。每次询问都枚举和式中的 \(j\)，然后计算即可。时间复杂度 \(\mathcal{O}((n+m)\sqrt{n})\)。
[AGC 023 E] Inversions
北大集训 2019 的题
给定正整数 \(d_1,d_2,\dots,d_n\)，求有多少个序列 \(\{a_n\}\) 满足：
- \(1\le a_i\)；
- \(a_i\mid d_i\)；
- \(\prod a_i\le \prod \frac{d_i}{a_i}\)。
可以发现 \(\prod a_i\le \prod \frac{d_i}{a_i}\) 和 \(\prod a_i\ge \prod \frac{d_i}{a_i}\) 的方案一一对应。假如总方案数是 \(S\)，\(\prod a_i=\prod \frac{d_i}{a_i}\) 的方案数是 \(C\)，那么答案就是 \(\frac{S+C}{2}\)。计算 \(C\) 时，因为每个素因子是独立的，所以分别背包即可。
二项式系数
P4351 [CERC2015]Frightful Formula
考虑每个 \(F(i,1)\) 对答案的贡献：这显然是 \(\binom{2n-2-i}{n-2}a^{n-1}b^{n-i}F(i,1)\)。\(F(1,i)\) 同理。
再考虑在 \((i,j)\) 处加上的 \(c\) 的贡献：\(c\times a^{n-i}b^{n-j}\binom{2n-i-j}{n-i}\)。这些 \(c\) 的总贡献是 \(\sum_{i=2}^n \sum_{j=2}^n c\times a^{n-i}b^{n-j}\binom{2n-i-j}{n-i}\)，令 \((i,j)\gets (n-i,n-j)\) 得
\[c\times\sum_{i=0}^{n-2} \sum_{j=0}^{n-2} a^{i}b^{j}\dbinom{i+j}{j}. \]令 \(f(k)=\sum_{j=0}^{n-2} b^j\binom{k+j}{j}\)，则化为
\[c\times\sum_{i=0}^{n-2} a^if(i). \]考虑 \(f(k)\) 如何递推（这种递推一般会用到加法恒等式）：
\[\begin{aligned} f(k+1)&=\sum_{j=0}^{n-2} b^j\binom{k+1+j}{j}\\ &=\sum_{j=0}^{n-2} b^j\left(\binom{k+j}{j}+[j>0]\binom{k+j}{j-1}\right)\\ &=f(k)+b\cdot f(k+1)-\binom{k+n-1}{n-2}. \end{aligned} \]移项得
\[f(k+1)=\frac{f(k)-\binom{k+n-1}{n-2}b^{n-1}}{1-b}. \]注意特判 \(b=1\) 的情况。于是就做完了。
P3726 [AHOI2017/HNOI2017] 抛硬币
直接硬推：
\[\begin{aligned} &\sum_{i=0}^a \sum_{j=0}^b \binom{a}{i}\binom{b}{j}[i>j]\\ &=\sum_{i=1}^a \sum_{j=0}^{a-i} \binom{a}{i+j}\binom{b}{j}\\ &=\sum_{i=1}^a \binom{a+b}{i+b}\\ &=\sum_{i=b+1}^{a+b} \binom{a+b}{i} \end{aligned} \tag{1} \]分类讨论，假如 \(a+b\) 是偶数，令 \(m=\frac{a+b}{2}\)，根据二项式系数的对称性得：
\[\begin{aligned} (1)&=\sum_{i=b+1}^{m} \binom{a+b}{i}+\sum_{i=m+1}^{a+b}\binom{a+b}{i}\\ &=\sum_{i=b+1}^{m} \binom{a+b}{i}+2^{a+b-1}-\frac{\binom{a+b}{m}}{2} \end{aligned} \]假如 \(a+b\) 是奇数，令 \(m=\lfloor\frac{a+b}{2}\rfloor\)：
\[\begin{aligned} (1)&=\sum_{i=b+1}^{m} \binom{a+b}{i}+\sum_{i=m+1}^{a+b}\binom{a+b}{i}\\ &=\sum_{i=b+1}^{m} \binom{a+b}{i}+2^{a+b-1} \end{aligned} \]因为 \(0
exLucas，狗都不写！
一个技巧：假如要表达 \(i>j\)，那么可以把 \(i\) 拆成 \(j+k\)，其中 \(k\) 是正整数。
Kummer 定理
对于正整数 \(n,m\) 和质数 \(p\)，\(\frac{(n+m)!}{n!m!}\) 中 \(p\) 的幂次等于在 \(p\) 进制下计算 \(n+m\) 时进位的次数。
证明似乎直接展开，然后利用 \(n\bmod p=n-p\lfloor\frac{n}{p}\rfloor\) 就行。