1000000007取模
时间: 2024-01-19 22:03:41 浏览: 35
对于大数取模的问题,常见的取模数是1000000007。这是因为1000000007是一个质数,并且它是最小的十位数的质数。对结果进行1000000007取模,可以保证值永远在int的范围之内,避免了大数越界的问题。
取模公式如下:
1. 两数相加再取模:(m + n) % p = (m%p + n%p) %p
2. 两数相乘再取模:(m * n) % p = (m%p) * (n%p) %p
3. 两数相减再取模:(m - n) % p = ((m%p - n%p) + p) %p
这些公式可以帮助我们在算法题中进行大数取模运算,确保结果的正确性。
相关问题
给定 n ,输出斐波那契数列的第 n 项,输出对 1000000007 取模,其中 F n =F n−1 +F n−2 ,F 1 =F 2 =1 输入格式: 给出一个正整数 n(1≤n≤10 4 ) 输出格式: 输出斐波那契数列的第 n 项,对 1000000007 取模
斐波那契数列是一个经典的递归问题,可以用递归函数的方式来求解,但是由于递归会重复计算很多次相同的数值,导致时间复杂度很高,因此我们可以使用动态规划的方法来避免这种重复计算。
具体地,我们可以用一个数组 `dp` 来存储斐波那契数列的前 n 项,其中 `dp[i]` 表示第 i 项的值。初始时,我们将 `dp[1]` 和 `dp[2]` 的值都初始化为 1,然后从 `dp[3]` 开始逐个计算,直到计算出 `dp[n]`。
为了防止数值溢出,我们需要对每个 `dp[i]` 取模 1000000007,这样计算过程中每个数的大小都不会超过这个值,从而保证结果的正确性。
下面是 Python 代码实现:
```python
n = int(input())
dp = [0] * (n + 1)
dp[1] = dp[2] = 1
for i in range(3, n + 1):
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])
```
这段代码首先读入一个正整数 `n`,然后初始化一个长度为 `n+1` 的数组 `dp`,将 `dp[1]` 和 `dp[2]` 的值都设为 1。接下来使用一个循环,从 `dp[3]` 开始逐个计算每个 `dp[i]` 的值,最后输出 `dp[n]` 即可。
“求有 n 个点 m 条边的无向连通图的个数,同时要求一号点的度数恰好为 2,输出答案要求对1000000007取模。用Python代码实现
以下是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),可以通过本题的测试数据。