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

Powered by:NEFU AB-IN

Link

3179. 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] 的值。

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

思路

杨辉三角是从第0行开始的。第0行只有一个元素，即1。然后每一行的开头和结尾都是1，中间的每个数是它上方两个数的和。

杨辉三角的例子

第 0 行: [1]
第 1 行: [1, 1]
第 2 行: [1, 2, 1]
第 3 行: [1, 3, 3, 1]
第 4 行: [1, 4, 6, 4, 1]

我们相当于计算的是杨辉三角第 n+k-1 排的第 n-1 个数，即 C(n+k-1, n-1)

代码

'''
Author: NEFU AB-IN
Date: 2024-07-11 16:48:47
FilePath: \LeetCode\3179\3179.py
LastEditTime: 2024-07-11 17:37:28
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, fabs, floor, gcd, log, sqrt, comb, perm
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(INF)


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])

    @staticmethod
    def to_1_indexed(data: Union[List, str, List[List]]):
        """Adds a zero prefix to the data and returns the modified data and its length."""
        if isinstance(data, list):
            if all(isinstance(item, list) for item in data):  # Check if it's a 2D array
                new_data = [[0] * (len(data[0]) + 1)] + [[0] + row for row in data]
                return new_data, len(new_data) - 1, len(new_data[0]) - 1
            else:
                new_data = [0] + data
                return new_data, len(new_data) - 1
        elif isinstance(data, str):
            new_data = '0' + data
            return new_data, len(new_data) - 1
        else:
            raise TypeError("Input must be a list, a 2D list, or a string")


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)

    class Mod:
        add = staticmethod(lambda *args: (lambda result=0: [(result := (result + num) % MOD) for num in args] and result)())
        sub = staticmethod(lambda a, b: (a - b + MOD) % MOD)
        mul = staticmethod(lambda *args: (lambda result=1: [(result := (result * num) % MOD) for num in args] and result)())
        div = staticmethod(lambda a, b: (a * pow(b, MOD - 2, MOD)) % MOD)
        mod = staticmethod(lambda a: (a % MOD + MOD) % MOD)


class Std:
    pass

# ————————————————————— Division line ——————————————————————


class Solution:
    def valueAfterKSeconds(self, n: int, k: int) -> int:
        nums = Arr.array(1, n)
        nums, n = Arr.to_1_indexed(nums)

        for _ in range(k):
            for i in range(1, n + 1):
                nums[i] = (nums[i] + nums[i - 1]) % MOD

        return nums[n]


class Solution:
    def valueAfterKSeconds(self, n: int, k: int) -> int:
        return comb(n + k - 1, n - 1) % MOD