二项式反演简略版

直接背式子就好了。

下三角:

[f[n]=sumlimits_{i=s}^n(-1)^icdotinom nicdot g[i]iff g[n]=sumlimits_{i=s}^n(-1)^icdot inom nicdot f[i] ]

常用形式:

[f[n]=sum_{i=s}^ninom nicdot g[i]iff g[n]=sum_{i=s}^n(-1)^{n-i}cdot inom nicdot f[i] ]


上三角:

[f[k]=sum_{i=k}^n(-1)^icdot inom ikcdot g[i]iff g[k]=sum_{i=k}^n(-1)^icdot inom ikcdot f[i] ]

常用形式:

[f[k]=sum_{i=k}^ninom ikcdot g[i]iff g[k]=sum_{i=k}^n(-1)^{i-k}cdot inom ikcdot f[i] ]


例题:

【BZOJ3622】已经没有什么好害怕的了

原文地址:https://www.cnblogs.com/Emiya-wjk/p/9987120.html