K 秒后第 N 个元素的值

100305. K 秒后第 N 个元素的值

给你两个整数 n 和 k。

最初，你有一个长度为 n 的整数数组 a，对所有 0 <= i <= n - 1，都有 a[i] = 1 。每过一秒，你会同时更新每个元素为其前面所有元素的和加上该元素本身。例如，一秒后，a[0] 保持不变，a[1] 变为 a[0] + a[1]，a[2] 变为 a[0] + a[1] + a[2]，以此类推。

返回 k 秒后 a[n - 1] 的值。

由于答案可能非常大，返回其对 10⁹ + 7 取余后的结果。

示例 1：

输入：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]

示例 2：

输入：n = 5, k = 3

输出：35

解释：

时间（秒）	数组状态
0	[1,1,1,1,1]
1	[1,2,3,4,5]
2	[1,3,6,10,15]
3	[1,4,10,20,35]

提示：

1 <= n, k <= 1000

相似题目

左右元素和的差值

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int valueAfterKSeconds(int n, int k) { } };

golang 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2024-06-10 00:30:38

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
}

java 解法, 执行用时: 2 ms, 内存消耗: 39.7 MB, 提交时间: 2024-06-10 00:30:23

class Solution {
    private static final int MOD = 1_000_000_007;
    private static final int MX = 2001;

    // 组合数模板
    private static final long[] FAC = new long[MX];
    private static final long[] INV_FAC = new long[MX];

    static {
        FAC[0] = 1;
        for (int i = 1; i < MX; i++) {
            FAC[i] = FAC[i - 1] * i % MOD;
        }
        INV_FAC[MX - 1] = pow(FAC[MX - 1], MOD - 2);
        for (int i = MX - 1; i > 0; i--) {
            INV_FAC[i - 1] = INV_FAC[i] * i % MOD;
        }
    }

    private static long comb(int n, int k) {
        return FAC[n] * INV_FAC[k] % MOD * INV_FAC[n - k] % MOD;
    }

    public int valueAfterKSeconds(int n, int k) {
        return (int) comb(n + k - 1, k);
    }

    private static long pow(long x, int n) {
        long res = 1;
        for (; n > 0; n /= 2) {
            if (n % 2 > 0) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
        }
        return res;
    }
}

cpp 解法, 执行用时: 0 ms, 内存消耗: 7.2 MB, 提交时间: 2024-06-10 00:30:06

const int MOD = 1'000'000'007;
const int MX = 2001;

long long q_pow(long long x, int n) {
    long long res = 1;
    for (; n > 0; n /= 2) {
        if (n % 2) {
            res = res * x % MOD;
        }
        x = x * x % MOD;
    }
    return res;
}

// 组合数模板
long long fac[MX], inv_fac[MX];

auto init = [] {
    fac[0] = 1;
    for (int i = 1; i < MX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    inv_fac[MX - 1] = q_pow(fac[MX - 1], MOD - 2);
    for (int i = MX - 1; i > 0; i--) {
        inv_fac[i - 1] = inv_fac[i] * i % MOD;
    }
    return 0;
}();

long long comb(int n, int k) {
    return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}

class Solution {
public:
    int valueAfterKSeconds(int n, int k) {
        return comb(n + k - 1, k);
    }
};

python3 解法, 执行用时: 43 ms, 内存消耗: 16.4 MB, 提交时间: 2024-06-10 00:29:53

class Solution:
    # 杨辉三角， 第 n+k 排的第 n 个数
    def valueAfterKSeconds(self, n: int, k: int) -> int:
        return comb(n + k - 1, k) % 1_000_000_007

上一题

下一题

详情