网站模板 在哪购买,沧州做网站的公司,钓鱼网站教程,wordpress 游戏 模板下载引入
二项式反演又名广义容斥定理 二项式反演可以表示成#xff1a; f[n]∑i0n(−1)iCnigi⟺gn∑i0n(−1)iCnif[i]f[n]\sum_{i0}^n(-1)^iC_{n}^{i}g_{i}⟺g_{n}\sum_{i0}^{n}(-1)^iC_{n}^{i}f[i]f[n]∑i0n(−1)iCnigi⟺gn∑i0n(−1)iCnif[i] 常用表达为#xff…引入
二项式反演又名广义容斥定理 二项式反演可以表示成 f[n]∑i0n(−1)iCnigi⟺gn∑i0n(−1)iCnif[i]f[n]\sum_{i0}^n(-1)^iC_{n}^{i}g_{i}⟺g_{n}\sum_{i0}^{n}(-1)^iC_{n}^{i}f[i]f[n]∑i0n(−1)iCnigi⟺gn∑i0n(−1)iCnif[i] 常用表达为 f[n]∑i0nCnig[i]⟺g[n]∑i0n(−1)n−iCnif[i]f[n]\sum_{i0}^{n}C_{n}^ig[i]⟺g[n]\sum_{i0}^{n}(-1)^{n-i}C_{n}^if[i]f[n]∑i0nCnig[i]⟺g[n]∑i0n(−1)n−iCnif[i] 证明详见二项式反演理解与证明
应用 恰好和至多的转换 设f[i]f[i]f[i]表示恰好的方案数g[i]g[i]g[i]表示至多的方案数则有g[n]∑i0nCni∗f[i]g[n]\sum_{i0}^nC_{n}^i*f[i]g[n]∑i0nCni∗f[i] 根据二项式反演有 f[n]∑i0n(−1)n−i∗Cni∗gif[n]\sum_{i0}^n(-1)^{n-i}*C_{n}^i*g_if[n]i0∑n(−1)n−i∗Cni∗gi gig_igi可以在很短的时间内求出再用g求f就得到答案 恰好和至少的转换 设f(i)表示恰好有i个的方案数g(i)至少有i个的方案数f(i)表示恰好有i个的方案数g(i)至少有i个的方案数f(i)表示恰好有i个的方案数g(i)至少有i个的方案数 有式子g(i)∑xinCxi∗f(x)g(i)\sum_{xi}^{n}C_{x}^i*f(x)g(i)∑xinCxi∗f(x) 根据二项式反演有 f(i)∑xin(−1)x−i∗Cxi∗g(x)f(i)\sum_{xi}^n(-1)^{x-i}*C_{x}^i*g(x)f(i)∑xin(−1)x−i∗Cxi∗g(x) 球染色问题n个球k个颜色求满足相邻颜色不同每种颜色至少出现一次的方案数 解决方案如果忽略每种颜色至少出现一次的限制那么方案数就是k(k−1)n−1k(k-1)^{n-1}k(k−1)n−1,就是一次安排颜色除了第一次k个随便放之后每次都是只能选k-1个(因为要和上一个不同) 设fif_ifi表示恰好使用i种颜色的方案数。gkg_kgk表示n个球用了k种颜色不强制每种颜色必须出现的方案数。那么问题就是求fnf_nfn 先将函数fff与ggg建立联系 g[k]k(k−1)n−1∑i0kCki∗f[i]g[k]k(k-1)^{n-1}\sum_{i0}^kC_{k}^i*f[i]g[k]k(k−1)n−1i0∑kCki∗f[i] 我们反演可得 f[k]∑i0kCki∗g[i]f[k]\sum_{i0}^{k}C_{k}^{i}*g[i]f[k]∑i0kCki∗g[i] f[k]∑i0kCki∗(−1)k−i∗g[i]f[k]\sum_{i0}^{k}C_{k}^i*(-1)^{k-i}*g[i]f[k]∑i0kCki∗(−1)k−i∗g[i]
例题
hdu P1465最不容易系列之一 luogu P4859 已经没有什么好害怕的了 [NOI Online #2 T3]游戏
