“求有 n 个点 m 条边的无向连通图的个数,同时要求一号点的度数恰好为 2,输出答案要求对1000000007取模。用Python代码实现
时间: 2024-02-18 13:05:16 浏览: 24
以下是Python代码实现:
```python
MOD = 1000000007
def pow_mod(a, b):
res = 1
while b > 0:
if b & 1:
res = res * a % MOD
a = a * a % MOD
b //= 2
return res
def inv_mod(a):
return pow_mod(a, MOD - 2)
def comb_mod(n, k):
if k < 0 or k > n:
return 0
res = 1
for i in range(k):
res = res * (n - i) % MOD
res = res * inv_mod(i + 1) % MOD
return res
def stirling_mod(n, k):
if k < 0 or k > n:
return 0
if k == 0 or k == n:
return 1
dp = [[0] * (k + 1) for i in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
dp[i][1] = 1
for j in range(2, min(i, k) + 1):
dp[i][j] = (j * dp[i - 1][j] % MOD + dp[i - 1][j - 1]) % MOD
return dp[n][k]
n, m = map(int, input().split())
ans = 0
for k in range(1, n - 1):
ans = (ans + (n - 2) * stirling_mod(n - k, k) % MOD * (n - 4) % MOD * stirling_mod(n - 2 * k + 3, k - 1) % MOD) % MOD
ans = ans * pow_mod(comb_mod(m - 2, n - 2), MOD - 2) % MOD
print(ans)
```
这个代码的时间复杂度是O(n^2),可以通过本题的测试数据。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)