小美的数组构造-美团笔试

小美拿到了一个数组，她准备构造一个数组 $b$ 满足：

1.$b$ 的每一位都和 $a$ 对应位置不同，即 $b_i≠a_i$
2.$b$ 的所有元素之和都和α相同。
3.$b$ 的数组均为正整数。

请你告诉小美有多少种构造方式。由于答案过大，请对 $10^9+7$ 取模。

输入描述

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

• $1≤n≤100$
• $1≤a_i≤300$
• $1≤\sum a_i ≤500$

输出描述

一个整数，代表构造方式对 $10^9+7$ 取模的值。

样例

输入
3
1 1 3

输出
1

样例解释
只有 [2,2,1] 满足条件。

输入
3
1 1 1

输出
0

说明
样例解释
没有满足条件的数组。

思路

主要是利用 dp 算法，dp[i][j]表示前i个数和为j的方案数，那么dp[i][j] = sum(dp[i-1][j-k])，其中k为 1 到j的数，但是要注意k不能等于a[i]，因为题目要求b[i]不能等于a[i]。

答案

n = int(input())
a = list(map(int, input().split()))
# n = 3
# a = [10, 3, 3]

MOD = 10**9 + 7

s = sum(a)

dp = [[0] * (s + 1) for _ in range(n + 1)]

dp[0][0] = 1

for i in range(1, n + 1):
    for j in range(1, s + 1):
        for k in range(1, j + 1):
            if k != a[i - 1]:
                dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD

print(dp[n][s])