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

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

@krydom1月前

05/17
20:19
Matrix-Tree定理 线性代数

[bzoj 4894] 天赋

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

小明有许多潜在的天赋,他希望学习这些天赋来变得更强。正如许多游戏中一样,小明也有n种潜在的天赋,但有一些天赋必须是要有前置天赋才能够学习得到的。也就是说,有一些天赋必须是要在学习了另一个天赋的条件下才能学习的。比如,要想学会"开炮",必须先学会"开枪"。一项天赋可能有多个前置天赋,但只需习得其中一个就可以学习这一项天赋。上帝不想为难小明,于是小明天生就已经习得了1号天赋-----"打架"。于是小明想知道学习完这n种天赋的方案数,答案对1,000,000,007取模。

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

第一行一个整数n。
接下来是一个n*n的01矩阵,第i行第j列为1表示习得天赋j的一个前置天赋为i。
数据保证第一列和主对角线全为0。
n<=300

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

第一行一个整数,问题所求的方案数。

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

8
01111111
00101001
01010111
01001111
01110101
01110011
01111100
01110110

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

72373

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

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

有向图的生成树(树形图)计数,直接matrix-tree定理

 

[bzoj 4894] 天赋