跳转至

3792. 递增乘积块之和 🔒

题目描述

给定一个整数 n。

一个序列的形成如下：

  • 第 1 块包含 1。
  • 第 2 块包含 2 * 3。
  • 第 i 块是之后 i 个连续整数的乘积。

令 F(n) 为前 n 块之和。

返回一个整数表示 F(n) 模上 109 + 7。

 

示例 1：

输入：n = 3

输出：127

解释：

  • 块 1：1
  • 块 2：2 * 3 = 6
  • 块 3：4 * 5 * 6 = 120

F(3) = 1 + 6 + 120 = 127

示例 2：

输入：n = 7

输出：6997165

解释：

  • 块 1：1
  • 块 2：2 * 3 = 6
  • 块 3：4 * 5 * 6 = 120
  • 块 4：7 * 8 * 9 * 10 = 5040
  • 块 5：11 * 12 * 13 * 14 * 15 = 360360
  • 块 6：16 * 17 * 18 * 19 * 20 * 21 = 39070080
  • 块 7：22 * 23 * 24 * 25 * 26 * 27 * 28 = 5967561600

F(7) = 6006997207 % (109 + 7) = 6997165

 

提示：

  • 1 <= n <= 1000

解法

方法一：模拟

我们可以直接模拟每一块的乘积并累加到答案中。需要注意的是，由于乘积可能会非常大，我们需要在每一步计算时对结果取模。

时间复杂度 \(O(n^2)\)，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def sumOfBlocks(self, n: int) -> int:
        ans = 0
        mod = 10**9 + 7
        k = 1
        for i in range(1, n + 1):
            x = 1
            for j in range(k, k + i):
                x = (x * j) % mod
            ans = (ans + x) % mod
            k += i
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int sumOfBlocks(int n) {
        final int mod = (int) 1e9 + 7;
        long ans = 0;
        int k = 1;
        for (int i = 1; i <= n; ++i) {
            long x = 1;
            for (int j = k; j < k + i; ++j) {
                x = x * j % mod;
            }
            ans = (ans + x) % mod;
            k += i;
        }
        return (int) ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int sumOfBlocks(int n) {
        const int mod = 1e9 + 7;
        long long ans = 0;
        int k = 1;
        for (int i = 1; i <= n; ++i) {
            long long x = 1;
            for (int j = k; j < k + i; ++j) {
                x = x * j % mod;
            }
            ans = (ans + x) % mod;
            k += i;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func sumOfBlocks(n int) (ans int) {
    const mod int = 1e9 + 7
    k := 1
    for i := 1; i <= n; i++ {
        x := 1
        for j := k; j < k+i; j++ {
            x = x * j % mod
        }
        ans = (ans + x) % mod
        k += i
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function sumOfBlocks(n: number): number {
    const mod = 1000000007;
    let k = 1;
    let ans = 0;
    for (let i = 1; i <= n; i++) {
        let x = 1;
        for (let j = k; j < k + i; j++) {
            x = (x * j) % mod;
        }
        ans = (ans + x) % mod;
        k += i;
    }
    return ans;
}

评论