BZOJ 组合数学题集

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

列表

[BZOJ 1005] [BZOJ 1008] [BZOJ 1042] [BZOJ 1211] [BZOJ 1485] [BZOJ 1856] [BZOJ 2339]
[BZOJ 2729] [BZOJ 2916] [BZOJ 2982] [BZOJ 3142] [BZOJ 3260] [BZOJ 3505] [BZOJ 3907]

简要题解

[BZOJ 1005] HNOI2008明明的烦恼

题解戳 >> http://codeplay0314.gitcafe.io/2015/06/22/BZOJ1005/

[BZOJ 1008] HNOI2008越狱

$ans=m^n-m*(m-1)^{n-1}$

[BZOJ 1042] HAOI2008硬币购物

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

[BZOJ 1485] HNOI2009有趣的数列

卡特兰数。

[BZOJ 1856] SCOI2010字符串

一一对应。

[BZOJ 2339] HNOI2011卡农

题解戳 >> http://codeplay0314.gitcafe.io/2015/09/16/BZOJ2339/

[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)$
高精度。

[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×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,高精度。