2025-01-14：K 秒后第 N 个元素的值。用go语言，给定两个整数 n 和 k，我们开始时有一个长度为 n 的整数数组
【摘要】 2025-01-14：K 秒后第 N 个元素的值。用go语言，给定两个整数 n 和 k，我们开始时有一个长度为 n 的整数数组 a，其中每个元素均为 1。在每秒的更新中，数组的每个元素都会被其前面所有元素的和与自身相加。经过一秒后，a[0] 不变，而 a[1] 变为 a[0] + a[1]，a[2] 变为 a[0] + a[1] + a[2]，依此类推。我们需要计算经过 k 秒后，a[n -...
2025-01-14：K 秒后第 N 个元素的值。用go语言，给定两个整数 n 和 k，我们开始时有一个长度为 n 的整数数组 a，其中每个元素均为 1。
在每秒的更新中，数组的每个元素都会被其前面所有元素的和与自身相加。
经过一秒后，a[0] 不变，而 a[1] 变为 a[0] + a[1]，a[2] 变为 a[0] + a[1] + a[2]，依此类推。
我们需要计算经过 k 秒后，a[n - 1] 的值，并将其对 1000000007 取模，然后返回结果。
1 <= n, k <= 1000。
输入：n = 4, k = 5。
输出：56。
解释：
时间（秒） 数组状态；
0 [1,1,1,1]；
1 [1,2,3,4]；
2 [1,3,6,10]；
3 [1,4,10,20]；
4 [1,5,15,35]；
5 [1,6,21,56]。
答案2025-01-14：
题目来自leetcode3179。
大体步骤如下：
-
在
main函数中，定义了输入的 n 和 k，然后调用valueAfterKSeconds函数，并打印最终结果。 -
在
init函数中，初始化了两个数组F和invF，它们分别用来存储阶乘值和阶乘值的逆元。其中F存储了 0 到 mx 的阶乘，invF存储了 mx 到 1 的阶乘的逆元。 -
pow函数用来计算 x 的 n 次方的结果，并且对 mod 取模。这个函数会在计算逆元的过程中使用。 -
valueAfterKSeconds函数用来计算经过 k 秒后第 n 个元素的值。首先计算出当前数组的值，然后按照规则更新数组 n+k-1 次，最终返回 a[n-1] 的值对 mod 取模的结果。
总的时间复杂度：
-
在
init函数中，计算 F、invF 数组的时间复杂度为 O(mx)，复杂度为 O(n)。 -
在
main函数中，调用valueAfterKSeconds函数的时间复杂度为 O(1)。 -
在
valueAfterKSeconds函数中，计算 a[n-1] 的时间复杂度为 O(n)，所以总的时间复杂度为 O(n)。
总的额外空间复杂度：
-
在
main函数中，除了 n 和 k 外没有额外的空间占用，复杂度为 O(1)。 -
在
init函数中，定义了 F 和 invF 两个数组来存储阶乘和逆元，空间复杂度为 O(n)。 -
在
valueAfterKSeconds函数中，除了常数项外并没有额外的空间占用，复杂度为 O(1)。
综上，总的时间复杂度为 O(n)，总的额外空间复杂度为 O(n)。
Go完整代码如下：
package main
import (
"fmt"
)
const mod = 1_000_000_007
const mx = 2000
var F, invF [mx + 1]int
func init() {
F[0] = 1
for i := 1; i <= mx; i++ {
F[i] = F[i-1] * i % mod
}
invF[mx] = pow(F[mx], mod-2)
for i := mx; i > 0; i-- {
invF[i-1] = invF[i] * i % mod
}
}
func valueAfterKSeconds(n, k int) int {
return F[n+k-1] * invF[n-1] % mod * invF[k] % mod
}
func pow(x, n int) int {
res := 1
for ; n > 0; n /= 2 {
if n%2 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}
func main() {
n := 4
k := 5
result := valueAfterKSeconds(n, k)
fmt.Println(result)
}
Rust完整代码如下：
const MOD: i64 = 1_000_000_007;
const MX: usize = 2000;
struct Combinatorics {
f: Vec<i64>,
inv_f: Vec<i64>,
}
impl Combinatorics {
fn new() -> Self {
let mut f = vec![1; MX + 1];
let mut inv_f = vec![1; MX + 1];
// Calculate factorials
for i in 1..=MX {
f[i] = f[i - 1] * i as i64 % MOD;
}
// Calculate inverse of factorials using Fermat's little theorem
inv_f[MX] = pow(f[MX], MOD - 2);
for i in (1..=MX).rev() {
inv_f[i - 1] = inv_f[i] * i as i64 % MOD;
}
Combinatorics { f, inv_f }
}
fn value_after_k_seconds(&self, n: usize, k: usize) -> i64 {
self.f[n + k - 1] * self.inv_f[n - 1] % MOD * self.inv_f[k] % MOD
}
}
fn pow(x: i64, n: i64) -> i64 {
let mut res = 1;
let mut base = x;
let mut exponent = n;
while exponent > 0 {
if exponent % 2 == 1 {
res = res * base % MOD;
}
base = base * base % MOD;
exponent /= 2;
}
res
}
fn main() {
let n = 4;
let k = 5;
let combinatorics = Combinatorics::new();
let result = combinatorics.value_after_k_seconds(n, k);
println!("{}", result);
}
C完整代码如下：
#include <stdio.h>
// #include <math.h>
#define MOD 1000000007
#define MX 2000
long long F[MX + 1], invF[MX + 1];
long long pow2(long long x, long long n) {
long long res = 1;
while (n > 0) {
if (n % 2 == 1) {
res = res * x % MOD;
}
x = x * x % MOD;
n /= 2;
}
return res;
}
void init() {
F[0] = 1;
for (int i = 1; i <= MX; i++) {
F[i] = F[i - 1] * i % MOD;
}
invF[MX] = pow2(F[MX], MOD - 2);
for (int i = MX; i > 0; i--) {
invF[i - 1] = invF[i] * i % MOD;
}
}
long long valueAfterKSeconds(int n, int k) {
return F[n + k - 1] * invF[n - 1] % MOD * invF[k] % MOD;
}
int main() {
int n = 4;
int k = 5;
init(); // 初始化阶乘和逆阶乘
long long result = valueAfterKSeconds(n, k);
printf("%lld\n", result);
return 0;
}
C++完整代码如下：
#include <iostream>
#define MOD 1000000007
#define MX 2000
long long F[MX + 1], invF[MX + 1];
// 快速幂计算
long long pow(long long x, long long n) {
long long res = 1;
while (n > 0) {
if (n % 2 == 1) {
res = res * x % MOD;
}
x = x * x % MOD;
n /= 2;
}
return res;
}
// 初始化阶乘和逆阶乘
void init() {
F[0] = 1;
for (int i = 1; i <= MX; i++) {
F[i] = F[i - 1] * i % MOD;
}
invF[MX] = pow(F[MX], MOD - 2);
for (int i = MX; i > 0; i--) {
invF[i - 1] = invF[i] * i % MOD;
}
}
// 计算值
long long valueAfterKSeconds(int n, int k) {
return F[n + k - 1] * invF[n - 1] % MOD * invF[k] % MOD;
}
int main() {
int n = 4;
int k = 5;
init(); // 初始化阶乘和逆阶乘
long long result = valueAfterKSeconds(n, k);
std::cout << result << std::endl;
return 0;
}
Python完整代码如下：
# -*-coding:utf-8-*-
MOD = 1_000_000_007
MX = 2000
# 阶乘和逆阶乘
F = [1] * (MX + 1)
invF = [1] * (MX + 1)
def pow(x, n):
res = 1
while n > 0:
if n % 2 == 1:
res = res * x % MOD
x = x * x % MOD
n //= 2
return res
def init():
global F, invF
for i in range(1, MX + 1):
F[i] = F[i - 1] * i % MOD
invF[MX] = pow(F[MX], MOD - 2)
for i in range(MX, 0, -1):
invF[i - 1] = invF[i] * i % MOD
def value_after_k_seconds(n, k):
return F[n + k - 1] * invF[n - 1] % MOD * invF[k] % MOD
if __name__ == "__main__":
n = 4
k = 5
init() # 初始化阶乘和逆阶乘
result = value_after_k_seconds(n, k)
print(result)
Solidity语言完整代码如下：
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
contract Calculate {
uint256 constant mod = 1_000_000_007;
uint256 constant mx = 2000;
uint256[mx + 1] private F;
uint256[mx + 1] private invF;
constructor() {
F[0] = 1;
for (uint256 i = 1; i <= mx; i++) {
F[i] = (F[i - 1] * i) % mod;
}
invF[mx] = pow(F[mx], mod - 2);
for (uint256 i = mx; i > 0; i--) {
invF[i - 1] = (invF[i] * i) % mod;
}
}
function valueAfterKSeconds(uint256 n, uint256 k) public view returns (uint256) {
require(n > 0 && k >= 0, "Invalid input values");
return (F[n + k - 1] * invF[n - 1] % mod * invF[k] % mod);
}
function pow(uint256 x, uint256 n) private pure returns (uint256) {
uint256 res = 1;
while (n > 0) {
if (n % 2 > 0) {
res = (res * x) % mod;
}
x = (x * x) % mod;
n /= 2;
}
return res;
}
// 主函数模拟，不能在智能合约中直接使用
function main() public view returns (uint256) {
uint256 n = 4;
uint256 k = 5;
return valueAfterKSeconds(n, k);
}
}
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）