思路：动态规划

给定一个数组$a$，要求构造出数组$b$满足以下约束：

1.$b_i \ne a_i$

2.$b$的所有元素之和都和a相同。

3.$b$的数组均为正整数。

求有多少种构造方式，答案对$10^9+7$取模

这道题是一道统计方法数类型的题目，且数据范围$n\le100,1 \leq a_i \leq 300,1 \leq \sum a_i \leq 500$，考虑到时间复杂度与题目类型，可以尝试往动态规划的方向思考。

定义：$dp[i][j]$表示前$i$个数的和为$j$的方法数有多少。

转移方程：$dp[i][j]=\sum\limits_{k< j\ \&\ j-k\neq a_i} {dp[i-1][k]}$

直观上理解就是，前$i$个数的和为$j$，我们在枚举前$i-1$个数的和$k$的同时，也是在枚举当前位置填放的数$j-k$，那么当前和为$j$的方法数，显然就是前$i-1$个数的情况和。

时间复杂度：$O(N*(\sum{a_i})^2)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n + 1);

    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
    }

    vector dp(n + 1, vector<int>(sum + 1));

    // dp[i][j] 前 i 个数，和为 j 的方案数
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= sum; ++j)
            for (int k = 1; k <= j; ++k)
                if (k != a[i])
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;

    cout << dp[n][sum] << "\n";

    return 0;
}

Python

MOD = int(1e9) + 7

n = int(input())
a = list(map(int, input().split()))

sum_val = 0
i = 1
while i <= n:
    sum_val += a[i - 1]
    i += 1

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

# dp[i][j] 前 i 个数，和为 j 的方案数
dp[0][0] = 1
i = 1
while i <= n:
    j = 1
    while j <= sum_val:
        k = 1
        while k <= j:
            if k != a[i - 1]:
                dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD
            k += 1
        j += 1
    i += 1

print(dp[n][sum_val])

Java

import java.util.Scanner;

public class Main {
    public static final int MOD = (int) 1e9 + 7;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int[] a = new int[n + 1];
        int sum = 0;
        for (int i = 1; i <= n; ++i) {
            a[i] = scanner.nextInt();
            sum += a[i];
        }

        int[][] dp = new int[n + 1][sum + 1];

        // dp[i][j] 前 i 个数，和为 j 的方案数
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= sum; ++j) {
                for (int k = 1; k <= j; ++k) {
                    if (k != a[i]) {
                        dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
                    }
                }
            }
        }

        System.out.println(dp[n][sum]);
    }
}

题目内容

小美有一个长度为 $n$ 的数组 $a$ ，现在他想要重新构造一个长度也为 $n$ 的数组 $b$ ，满足如下三个条件，就是小美要构造的数组 $b$ 。

• $\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^n b_i$

• $a_i\neq b_i (1\leq i\leq n)$

• $b_i > 0$

现在小美想问你，可以构造出多少种不同的数组 $b$ ，答案对 $10^9+7$ 取模。

输入描述

第一行，一个正整数 $n(1\leq n\leq 100)$ ，表示数组 $a$ 和 $b$ 的大小

第二行，$n$ 个正整数 $a_i(1\leq a_i\leq 300, \sum\limits_{i=1}^n a_i\leq 500)$

输出描述

输出一个整数，表示构造出的不同的数组 $b$ 的方案数，答案对 $10^9+7$ 取模。

样例

输入

3
1 2 3

输出

3