[DP]bzoj:1079 [SCOI2008]着色方案

04 January 2018

有n个木块排成一行,从左到右依次编号为1~n。你有k种颜色的油漆,其中第i种颜色的油漆足够涂ci个木块。

所有油漆刚好足够涂满所有木块,即c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看,所以你希望统计任意两个相邻木块颜色不同的着色方案。

[数论]bzoj 1008: [HNOI2008]越狱

08 January 2018

监狱有连续编号为1...N的N个房间,每个房间关押一个犯人,有M种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱

矩阵树定理

03 July 2018

矩阵树定理,又称基尔霍夫定理,是用来求一个图中生成树的数量。