ZZULIOJ

问题3027--对抗环

时间限制: 1 Sec 内存限制: 128 MB
提交: 85 解决: 19
[状态] [讨论版] [提交] [命题人:]

题目描述

在一个环上有

n

个空，需要将

0 \to 9

的数字填入其中
可是数字之间存在对抗性，现给定

m

对对抗数字，对于每一对

(x, y)

，他们在被填入环时均不能相邻
问有多少种方案填满整个环（答案模上

109 + 7

）

输入

第一行两个整数 $n, m (2 \leq n \leq 100, 0 \leq m \leq 55)$
接下来 $m$ 行，每行两个一位非负整数 $x, y$ ，表示 $x$ 和 $y$ 不能相邻

输出

输出一个非负整数表示方案数模上

109 + 7

的值

样例输入 Copy

2 2
0 1
5 2

样例输出 Copy

提示

顺时针填数方案从

00

到

99

一共

100

种，少了

{01, 10, 52, 25}

四种

来源/分类

[提交] [状态]