形式1
g(i) 表示 n 个条件，恰好满足 i 个的情况数，的总和
恰好不好求，因为不仅需要 i 个满足，而且需要 n-i 个不满足
以下的图n=3，
g(1)
g(2)
g(3)
f(k) 表示选择 k 个满足，剩下 n-k 个随意的情况数，的总和
f(1)= 三个圆形面积的和 =g(1)+2g(2)+3g(3)
通常情况是 f 可以DP算出来，然后通过以下公式反演出 g
f(k)=\sum\{i=k}^n \ ik g(i)
g(k)=\sum\{i=k}^n (-1)^{i-k}\ ikf(i)
形式2
g(i) 表示 n 个条件，恰好满足 i 个的情况数，但不是总和
g(1)
g(2)
g(3)
f(k) 表示选择 k 个满足，剩下 n-k 个随意的情况数，但不是总和
f(3)= 三个圆形面积的并 =3g(1)+3g(2)+g(3)
通常情况是 f 可以组合数学或者DP算出来，然后通过以下公式反演出 g
f(k)=\sum\{i=m}^{k} \ ki g(i)
g(k)=\sum\{i=m}^k (-1)^{k-i}\ kif(i)
个人感觉对满足条件个数相同，条件序号选择不同，g(i)相等时用形式2，否则用形式1
比如g(1)选左下还是上面还是右下的数量都一样，那么用形式2
形式2例题：
luogu p5505
形式1例题：
luogu p4859
luogu p6478
本文使用 Zhihu On 创作并发布
