BZOJ 组合数学题集

最近做了一大波组合数学水题…加上以前的一些…做成一个集合。
好多省选题啊…HN最近考得比较多？

[BZOJ 1005] HNOI2008明明的烦恼

题解戳 >> 1005 HNOI2008 明明的烦恼

[BZOJ 1008] HNOI2008越狱

ans=mn−m∗(m−1)n−1ans=m^n−m∗(m−1)^{n−1}

[BZOJ 1042] HAOI2008硬币购物

DP+容斥。
先算出所有可能方案，容斥计算不合法方案。

[BZOJ 1485] HNOI2009有趣的数列

卡特兰数。

[BZOJ 1856] SCOI2010字符串

一一对应。

[BZOJ 2339] HNOI2011卡农

题解戳 >> 2339 HNOI2011 卡农

[BZOJ 2729] HNOI2012排队

ans=m×(n+1)!×2×(m−1)!×C(n+2,m−1)+((n+2)!−(n+1)!×2)×m!×C(n+3,m)ans=m×(n+1)!×2×(m−1)!×C(n+2,m−1)+((n+2)!−(n+1)!×2)×m!×C(n+3,m)
高精度。

[BZOJ 2916] Monochromatic Triangles

考虑反向问题，即不同色三角形。
总三角形为n(n-1)(n-2)/6，某个顶点所在的不同色三角形数为red[i]×blue[i]/2，计算即可。但注意取整问题，运算上现在*2基础上进行，最后/2。

[BZOJ 2982] combination

傻逼题。

[BZOJ 3142] HNOI2013数列

ans=n×mk−1−m×(m+1)/2×mk−2×(k−1)ans=n×m^{k−1}−m×(m+1)/2×m^{k−2}×(k−1)

[BZOJ 3260] 跳

题解戳 >> http://www.cnblogs.com/xkui/p/4587411.html

[BZOJ 3505] CQOI2014数三角形

计算所有可能减去三点共线的情况。GCD.

[BZOJ 3907] 网格

同1856，高精度。

Comment