2025-01-14：K 秒后第 N 个元素的值。用go语言，给定两个整数 n 和 k，我们开始时有一个长度为 n 的整数数组

福大大架构师每日一题

发布于 2025-01-15 22:05:01

6100

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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：

chatgpt[1]

题目来自leetcode3179。

大体步骤如下：

1. 在 main 函数中，定义了输入的 n 和 k，然后调用 valueAfterKSeconds 函数，并打印最终结果。
2. 在 init 函数中，初始化了两个数组 F 和 invF，它们分别用来存储阶乘值和阶乘值的逆元。其中 F 存储了 0 到 mx 的阶乘，invF 存储了 mx 到 1 的阶乘的逆元。
3. pow 函数用来计算 x 的 n 次方的结果，并且对 mod 取模。这个函数会在计算逆元的过程中使用。
4. 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;

structCombinatorics {
    f: Vec<i64>,
    inv_f: Vec<i64>,
}

implCombinatorics {
    fnnew() ->Self {
        letmut f = vec![1; MX + 1];
        letmut inv_f = vec![1; MX + 1];

        // Calculate factorials
        foriin1..=MX {
            f[i] = f[i - 1] * i asi64 % MOD;
        }

        // Calculate inverse of factorials using Fermat's little theorem
        inv_f[MX] = pow(f[MX], MOD - 2);

        foriin (1..=MX).rev() {
            inv_f[i - 1] = inv_f[i] * i asi64 % MOD;
        }

        Combinatorics { f, inv_f }
    }

    fnvalue_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
    }
}

fnpow(x: i64, n: i64) ->i64 {
    letmut res = 1;
    letmut base = x;

    letmut exponent = n;
    while exponent > 0 {
        if exponent % 2 == 1 {
            res = res * base % MOD;
        }
        base = base * base % MOD;
        exponent /= 2;
    }

    res
}

fnmain() {
    letn = 4;
    letk = 5;

    letcombinatorics = Combinatorics::new();
    letresult = combinatorics.value_after_k_seconds(n, k);
    println!("{}", result);
}

C完整代码如下：

#include <stdio.h>
// #include <math.h>
#define MOD 1000000007
#define MX 2000

longlong F[MX + 1], invF[MX + 1];

longlongpow2(long long x, long long n) {
    longlong res = 1;
    while (n > 0) {
        if (n % 2 == 1) {
            res = res * x % MOD;
        }
        x = x * x % MOD;
        n /= 2;
    }
    return res;
}

voidinit() {
    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;
    }
}

longlongvalueAfterKSeconds(int n, int k) {
    return F[n + k - 1] * invF[n - 1] % MOD * invF[k] % MOD;
}

intmain() {
    int n = 4;
    int k = 5;

    init(); // 初始化阶乘和逆阶乘
    longlong result = valueAfterKSeconds(n, k);
    printf("%lld\n", result);

    return0;
}

C++完整代码如下：

#include <iostream>
#define MOD 1000000007
#define MX 2000

longlong F[MX + 1], invF[MX + 1];

// 快速幂计算
long long pow(long long x, long long n) {
    longlong 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(); // 初始化阶乘和逆阶乘
    longlong result = valueAfterKSeconds(n, k);
    std::cout << result << std::endl;

    return0;
}

Python完整代码如下：

# -*-coding:utf-8-*-

MOD = 1_000_000_007
MX = 2000

# 阶乘和逆阶乘
F = [1] * (MX + 1)
invF = [1] * (MX + 1)

defpow(x, n):
    res = 1
    while n > 0:
        if n % 2 == 1:
            res = res * x % MOD
        x = x * x % MOD
        n //= 2
    return res

definit():
    global F, invF
    
    for i inrange(1, MX + 1):
        F[i] = F[i - 1] * i % MOD
        
    invF[MX] = pow(F[MX], MOD - 2)
    
    for i inrange(MX, 0, -1):
        invF[i - 1] = invF[i] * i % MOD

defvalue_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;
        }
    }

    functionvalueAfterKSeconds(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);
    }

    functionpow(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;
    }

    // 主函数模拟，不能在智能合约中直接使用
    functionmain() public view returns (uint256) {
        uint256 n = 4;
        uint256 k = 5;
        returnvalueAfterKSeconds(n, k);
    }
}