题解 P6076【[JSOI2015]染色问题】

· · 题解

设 h(x) 为至多用 x 种颜色的方案数，p(x) 为恰好用 x 种颜色的方案数。则有：

h(c) = \sum\limits_{i=0}^c \dbinom{c}{i} p(i)

反演得：

p(c) = \sum\limits_{i=0}^c(-1)^{c-i} \dbinom{c}{i} h(i)

在保证每行都会被染的情况下，f(x) 为至多使用 i 种颜色，至多保证 x 列合法的方案数，g(x) 为恰好保证 x 列合法的方案数。则有：

f(m) = \sum\limits_{j=0}^m \dbinom{m}{j} g(j)

反演得：

g(m) = \sum\limits_{j=0}^m(-1)^{m-j} \dbinom{m}{j} f(j)

其中

f(k) = ((i+1)^k-1)^n

考虑每个格子有 i + 1 种方案，每行有 k 个要染的，再减去全为 0 的方案即可。

综上：

ans = \sum\limits_{i=0}^c(-1)^{c-i} \dbinom{c}{i} h(i) h(i) = \sum\limits_{j=0}^m(-1)^{m-j} \dbinom{m}{j} ((i+1)^j-1)^n