抽象地，定义 \(g_i\) 表示选 \(i\) 个位置对应的结果，假设答案的式子为
\[ans = \sum_{i=0}^n g_i \theta^i \]可以直接在 \(\text{dp}\) 的过程中维护 \(\theta^i\)，即，每多选一个位置就将转移系数乘上 \(\theta\)。
但是在某一类特殊的计数题中，我们遇到了这样的问题：我们无法直接求出 \(g\)，需要先求出 \(h\)，且 \(h\) 二项式反演后得到 \(g\)。若在 \(\text{dp}\) 的过程中多维护钦定的位置的数量，会多一个维度造成复杂度劣化。事实上，我们有
\[\begin{aligned} ans &= \sum_{i=0}^n g_i \theta^i \\&= \sum_{i=0}^n \sum_{j=i}^n (-1)^{j-i} {j \choose i} h_j \theta^i \\&= \sum_{j=0}^n \sum_{i=0}^j {j \choose i}(-1)^{j-i} \theta^i h_j \\ &=\sum_{j=0}^n h_j(\theta-1)^j \end{aligned} \]与求 \(\sum_{i=0}^n g_i \theta^i\) 的原问题等价，我们只需要将多选一个位置产生的转移系数由 \(\theta\) 改为 \(\theta-1\) 就好了。
标签：技巧,text,sum,计数,choose,ans,theta,有趣 From： https://www.cnblogs.com/ducati/p/17133649.html