关于二项式反演的一些思考

关于二项式反演的一些思考

今天T2考了二项式反演,转化之后要求的是n个非负整数的和为m,求其中有至少k个数\(\geq l\)的方案数。

感觉是二项式反演,然后一看题解——至少是恰好的后缀和,仔细想想也没什么问题。可之前看的二项式反演博客里至少和恰好都是这样的关系:

\[f(i)_\text{至少}=\sum_{j\geq i}^n {j\choose i} g(j)_\text{恰好} \]

想了一会之后发现,二项式反演的“至少“不太像”至少",而应该是”钦定“的关系。在这道题中,\(k+1\)个数\(\geq l\)的方案减去\(k\)个\(l\)成为被组合数统计的非负整数插板,就有\(k+1\choose k\)种情况。由于一种方案可能有多种钦定情况,也就不是后缀和而是二项式反演的组合数加权和形式。

所以应该是

\[f(i)_\text{钦定}=\sum_{j\geq i}^n {j\choose i} g(j)_\text{恰好} \]

上一篇:IOI2000 邮局


下一篇:上界、下界和准确界