#P2169. 连边

    ID: 1193 传统题 1000ms 259MiB 尝试: 374 已通过: 191 难度: 8 上传者: 标签>CF2500提高+/省选-计数 DP奇偶性分析双射计数逆元线性递推滚动数组版权所有者:范浩强

连边

题目描述

有 nn 个点(编号 11 到 nn)组成的无向图,已经为你连了 mm 条边。请你再连 kk 条边,使得所有的点的度数都是偶数。求有多少种连的方法。

要求你连的 kk 条边中不能有重边,但和已经连好的边可以重。不允许自环的存在。求连边的方法数。我们只关心它模 1000710007 的余数。

输入格式

输入的第一行有三个自然数,分别表示点数 nn,已经连好的边数 mm,和你要连的边数 kk。保证 k≤n(n−1)2k\leq \frac{n(n-1)}2。

接下来 mm行每行两个整数 x,yx,y,描述了一条连接 xx 和 yy 的边。

输出格式

输出一个整数,表示连边的方法数模 1000710007 的余数。

样例输入

5 1 4
1 2

样例输出

13

样例说明

以下是 1313 种连边的方法(只显示你连的边):

{(1,2),(1,3),(1,4),(3,4)}
{(1,2),(1,3),(1,5),(3,5)}
{(1,2),(1,4),(1,5),(4,5)}
{(1,2),(2,3),(2,4),(3,4)}
{(1,2),(2,3),(2,5),(3,5)}
{(1,2),(2,4),(2,5),(4,5)}
{(1,2),(3,4),(3,5),(4,5)}
{(1,3),(2,4),(3,5),(4,5)}
{(1,3),(2,5),(3,4),(4,5)}
{(1,4),(2,3),(3,5),(4,5)}
{(1,4),(2,5),(3,4),(3,5)}
{(1,5),(2,3),(3,4),(4,5)}
{(1,5),(2,4),(3,4),(3,5)}

数据规模与约定

30%30\% 的数据满足:n≤200n\leq 200。

100%100\% 的数据满足:n≤103n\leq 10^3,m≤n,k≤min⁡(103,n(n−1)2)m\leq n,k\leq \min(10^3,\frac{n(n-1)}2)。

(修着按:在修缮本题时,发现了在题目末尾的另一段数据范围,经测试,该数据范围与数据不符,现将其附于下方:

对于 20%20\% 的数据,4≤n≤1004\leq n\leq 100。

对于 40%40\% 的数据,4≤n≤5×1034\leq n\leq 5\times 10^3。

对于 100%100\% 的数据,4≤n≤5×1044\leq n\leq 5\times 10^4,1≤m≤101\leq m\leq 10,m≤nm\leq n,所有出现的整数均不超过 3232 位含符号整数。 )

题目来源

版权所有者:范浩强