计数问题的思考方法
——以《[ARC102E] Stop. Otherwise...》为例
DP
如果要使用 DP，则重点在其状态的设计，即我已经考虑了什么，当前正在考虑什么，通过一个不断将考虑范围扩大的方法，得到答案。
在转移的过程中，往往通过当前决策点的不同状态，从不同的状态转移过来（或转移到不同的状态），以得到不同的方案数。
最后根据转移方程进行优化。
DP的优势在于灵活，使得其可以应对各种复杂的问题。
在这道题中， \(f_{i,j}\) 表示考虑前 \(i\) 对数，选择了 \(j\) 个数的方案数。那么这对数可以不选，或者选 \(1\) 个，\(2\) 个， \(3\) 个……以此进行转移。同理 \(g_{i,j}\) 表示考虑了 \(i\) 个没有限制的数，其中选择了 \(j\) 个的方案数。对转移前缀和优化即可在时间限制内得到答案。
参考：[AT4362] [ARC102C] Stop. Otherwise... - 洛谷专栏 (luogu.com.cn)
组合计数
即直接考虑将题目抽象为组合式，再以数学方法或预处理等算法进行优化。
如果要使用这种方法，一定要使用正确的组合意义与推式子技巧，在枚举的时候应该使用组合意义相近的变量，使得式子得到简化。
组合计数的优势在于简单易懂，只要式子推对了，不容易出错。
对于这道题而言，对与计算和不等于 \(s\) 的答案，可以直接枚举出现了几种点对，有式子：
\[\begin{aligned} ans&=\sum_{i=0}^{s}\sum_{j=0}^s{n-1\choose i+j-1}{s\choose i}{k-2s\choose j}2^i \\&=\sum_{i=0}^{s}2^i{s\choose i}\sum_{j=0}^{k-2s}{n-1\choose n-i-j}{k-2s\choose j} \\&=\sum_{i=0}^s2^i{s\choose i}{n-1+k-2s\choose n-i} \end{aligned} \]最后一步由范德蒙德下指标卷积可得，单次复杂度 \(\mathcal O(s)\) 可以计算。
其实这道题有很多种但是这一种，由于所枚举的 \(i,j\) 是意义相关的两种（即特殊的选择几种，非特殊的选择几种），所以其表达式类似，往往可以简单的进行优化。
不用最后一步的暴力方法需要对 \(k<2s\) 特判，但最后使用了卷积后就不用了。
附上常用组合公式：
范德蒙德卷积及其推论：如果两个都为正，可以利用 \({n\choose m}={n\choose n-m}\) 将其中一个取反。
\[\sum_{i=0}^{r}{n\choose i}{m\choose r-i}={n+m\choose r} \\\sum_{i=-r}^s{n\choose r+i}{m\choose s-i}={n+m\choose r+s} \]错位式：
\[{n\choose r}{r\choose k}={n\choose k}{n-k\choose r-k} \]连续上指标求和：
\[\sum_{l=k}^n{l\choose k}={n+1\choose k+1} \]带权和：
\[\sum_{i=0}^ni^k{n\choose i}=n^{\overline k}2^{n-k} \]参考：
ARC102E Stop. Otherwise... 题解 - 洛谷专栏 (luogu.com.cn)
生成函数
生成函数最关键的就是考虑清楚对象与大小函数，通过多项式的运算得到答案。
统计取到一定大小函数的方案数。
生成函数的优势在于推导方式灵活，较不容易出错，并且可以使用 \(FFT\) 优化到 \(\mathcal O(n\log n)\)
比如这道题，考虑不能出现的数为奇数 \(X=2s+1\) 的情况，，观察有限制的数组这一对象，其为 \(\{i,T-i\}\) 这个组，我们可以当作一个处理，最后再乘以二，则其为 \(A(x)= x\)，即大小函数为 \(1\) ,方案数为 \(1\)。
那么对其进行 \(\text{SEQ}\) 构造，则 \(\text{SEQ}(A(x))=\frac 1{1-A(x)}=\frac 1{1-x}\)，最后乘二，但是不选的那种算重了，所以生成函数为 \(\text{SEQ}(B(x))=\frac 2{1-x}-1=\frac {1+x}{1-x}\)。对于没有特殊限制的组，其为 \(\text{SEQ}(B(x))=\frac{1}{1-x}\)，最后答案是整个对象的 \(\text{MEST}\) 构造，即 \(\text{SEQ}\) 构造的乘积，最后为 \((\frac {1-x}{1+x})^{s}(\frac 1{1-x})^{k-2s}\)，偶数的情况稍作特判可得。
直接动态维护上述式子做到 \(\mathcal O(nk)\)。
参考：
题解：AT_arc102_c [ARC102E] Stop. Otherwise... - 洛谷专栏 (luogu.com.cn)
容斥反演
容斥是通过其实是通过数学原理简化限制，从全部满足，变成存在一个不满足。
使用容斥也需要找到真正的限制对象是什么，做到刚好不满足，可以将复杂的限制容斥掉，保留简单的，容易满足的限制以符合定义，得到正确的答案。
容斥原理的优势在于避其锋芒，可以有效的转化限制，处理全部要求类的问题。
反演则是容斥的进一步深化，特殊化，总结出固定的式子，做到恰好，至多，至少之间的转化。
这道题使用容斥原理，设 \(x=2s+1\)，则钦定有 \(i\) 组数不能选的方案数，答案为：
\(\sum_{i=1}^s(-1)^i{s\choose i}2^{x-i}{K-s-i-2+n\choose n}\)，对于 \(x\) 为偶数的情况同理特判加上选择 \(\frac x2\) 的方案数。
参考：容斥原理、ARC102C 题解 - 洛谷专栏 (luogu.com.cn)
标签：frac,2s,text,sum,容斥,choose,思考,计数问题,方法 From： https://www.cnblogs.com/lupengheyyds/p/18540423