Skip to content

1426: イレイナ画结界

题目

题目描述

伊蕾娜是一位魔女,因为向往着幼时读过的旅行故事,她踏上了漫长的旅途,与形形色色的国家与人们邂逅。

这一次,她来到了一个常年遭到野兽袭击的国家,为了感谢国王的款待,她决定帮这个国家创造一个可以抵御野兽入侵的结界。

伊蕾娜已经围绕国家布下了结界的 $n$ 个节点,可以认为这些节点是均匀分布在一个圆上的。现在伊蕾娜需要给这 $n$ 个结界节点之间连接 $n - 1$ 条魔法线,使得这 $n$ 个节点是连通的。

根据结界的要求,这 $n - 1$ 条魔法线必须不能相交,并且节点间不同的连线方法会得到不同效果的结界。伊蕾娜知道防御结界的要求是对于一些特定的节点,不能用魔法线将它们直接相连(也就是它们之间只能间接相连)。

伊蕾娜愿意将防御结界的要求教给你,但是作为交换她想知道有多少种不同的防御结界,你能告诉她吗?

两种结界被认为是不同的当且仅当存在两个节点在其中一个结界中被魔法线直接相连而在另一个中没有。

由于答案可能很大,只需要输出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行一个整数 $n$ 表示结界的节点个数。

接下来 $n$ 行,每行 $n$ 个数。如果第 $i$ 行第 $j$ 列的数 $a_{i, j} = 0$,那么节点 $i$ 和节点 $j$ 就不能被魔法线直接相连,否则 $a_{i, j} = 1$。

保证 $a_{i, j} = a_{j, i}$,并且 $a_{i, i} = 0$。

输出格式

输出所有可能的防御结界个数对 $10^9 + 7$ 取模的结果。

样例输入

样例输入 1

text 3 0 0 1 0 0 1 1 1 0

样例输入 2

text 4 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0

样例输出

样例输出 1

text 1

样例输出 2

text 12

数据范围

对于 $20\%$ 的数据,$1\leq n \leq 10$

对于 $50\%$ 的数据,$1\leq n \leq 50$

对于 $100\%$ 的数据,$1\leq n \leq 500$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!