CF404 Div.2

发表于 | 更新于

Link

D

比赛直到还剩十分钟的时候才考虑到要化组合数的式子，之前一直觉得组合数的方法不可想因为涉及到组合数就需要长度就需要枚举，然后一直在想怎么可以不看长度算贡献。。。这就是思维漏洞。。

范德蒙恒等式

∑Cnk−iCmi=Cn+mk\sum C_{n}^{k-i}C_{m}^i=C_{n+m}^k

证明

考虑二项式展开:(a+b)n=∑i=0nCniaibn−i(a+b)^n=\sum\limits_{i=0}^nC_n^ia^ib^{n-i} 带入得到 (a+b)n(a+b)m=∑i=0nCniaibn−i∑j=0mCmjajbm−j(a+b)^n(a+b)^m=\sum\limits_{i=0}^nC_n^ia^ib^{n-i}\sum\limits_{j=0}^mC_m^ja^jb^{m-j} =(a+b)n+m=∑i=0n+mCn+miaibn+m−i=(a+b)^{n+m}=\sum\limits_{i=0}^{n+m}C_{n+m}^ia^ib^{n+m-i} 令b=1b=1，就可以得到aia^i的系数为 ∑n+mi=∑CnjCmi−j\sum_{n+m}^i=\sum C_n^jC_m^{i-j} 然后，∑Ca−1i−1Cbi=∑Ca−1a−iCbi=Ca+b−1a\sum C_{a-1}^{i-1}C_b^i=\sum C_{a-1}^{a-i}C_b^i=C_{a+b-1}^a

E

现在看写这个比刚D题性价比更高。。 树状数组套线段树，时空O(qlog2n)O(q\log^2n)