首页 > 试题广场 >

小美的数组构造

[编程题]小美的数组构造

热度指数：1038 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美拿到了一个数组 $a$ ，她准备构造一个数组 $b$ 满足：
1. $b$ 的每一位都和 $a$ 对应位置不同，即 $b_i ≠ a_i$
2. $b$ 的所有元素之和都和 $a$ 相同。
3. $b$ 的数组均为正整数。
请你告诉小美有多少种构造方式。由于答案过大，请对 $10^9+7$ 取模。

输入描述:

第一行输入一个正整数，代表数组的大小。
第二行输入个正整数，代表小美拿到的数组。

输出描述:

一个整数，代表构造方式对取模的值。

示例1

输入

3
1 1 3

输出

说明

只有[2,2,1]这一种数组合法。

示例2

输入

3
1 1 1

输出

算法知识视频讲解

Python

当一个da

import sys

for i, line in enumerate(sys.stdin):
    if i == 0:
        n = int(line)
    else:
        nums = [int(num) for num in line.split()]

total = sum(nums)
# 创建dp表
dp = [[0] * (total + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, total + 1):
        if i == 1:
            if j != nums[i-1]:
                dp[i][j] = 1
            else:
                dp[i][j] = 0
        else:
            dp[i][j] = (sum(dp[i-1][0:j]) - dp[i-1][j-nums[i-1]]) if (j - nums[i-1]) > 0 else 
            sum(dp[i-1][0:j])


print(dp[n][total] % (10**9+7))

编辑于 2024-03-16 11:48:43 回复(0)