Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

09/11
12:38
快速幂 组合数/lucas

[bzoj 4487] [Jsoi2015]染色问题

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 棋盘是一个n×m的矩形,分成n行m列共n*m个小方格。现在萌萌和南南有C种不同颜色的颜料,他们希望把棋盘用这些颜料染色,并满足以下规定:
1.  棋盘的每一个小方格既可以染色(染成C种颜色中的一种) ,也可以不染色。
2.  棋盘的每一行至少有一个小方格被染色。
3.  棋盘的每一列至少有一个小方格被染色。
4.  种颜色都在棋盘上出现至少一次。
以下是一些将3×3棋盘染成C = 3种颜色(红、黄、蓝)的例子:
aa1
请你求出满足要求的不同的染色方案总数。只要存在一个位置的颜色不同,
即认为两个染色方案是不同的

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

输入只有一行 3 个整数n,m,c。1 < = n,m,c < = 400

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出一个整数,为不同染色方案总数。因为总数可能很大,只需输出总数
mod 1,000,000,007的值。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

2 2 3

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

60

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

sro Nirobc orz

http://blog.csdn.net/nirobc/article/details/51064832

c++:

pascal:

 

[bzoj 4487] [Jsoi2015]染色问题