[IOI Camp Judge 60]背包 EX（駭客題）(題目備份)

IOI Camp Judge是暫時性的，因此在此作題目備份
題解在這裡

背包 EX（駭客題）

Time Limit: 1s

Original Description

天秤女孩阿斯特莉亞收到了一個精美的天平作為她的生日禮物，開心的她馬上將一個重量 m$m$ 克的砝碼放入其中一側，天平便漸漸傾斜了。

阿斯特莉亞看著傾斜的天平和手邊 n$n$ 個重量分別為 a1,a2,…,an$a_1,a_2,\dots ,a_n$ 克的砝碼，忍不住想：「有沒有辦法從這些砝碼中挑一些放到另外一側，使得天平回到平衡的狀態呢？有辦法的話又有幾種不同的挑法呢？」

Original Input Format

第一行有一個正整數 T$T$，代表總共有幾筆測試資料。每筆測試資料第一行為兩個整數 n,m$n,m$，第二行為 n$n$ 個整數 a1,a2,…,an$a_1,a_2,\dots ,a_n$。

• 1≤T≤100$1\le T\le 100$
• 1≤n≤$1\le n\le$ 生命、宇宙以及任何事情的終極答案
• 1≤m≤777$1\le m\le 777$
• 1≤ai≤m$1\le a_i\le m$
• 所有砝碼重量皆相異

Original Output Format

對於每筆測試資料，請輸出一行一個整數，代表有幾種挑法可以使得天平回到平衡的狀態。由於答案可能很大，請輸出該數除以 1000000007$1000000007$ 的餘數。

Sample Input

2
3 3
1 2 3
4 13
1 2 4 8

Sample Output

2
1

Hacked Program

#include <cstdio>
 
const int N = 42;
const int M = 777;
const int MOD = 1e9 + 7;
 
int t, n, m, a[N], dp[M + 1];
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) scanf("%d", a + i);
        for (int i = 0; i <= m; i++) dp[i] = 0;
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= a[i]; j--) {
                dp[j] += dp[j - a[i]];
                if (dp[j] > MOD) dp[j] -= MOD;
            }
        }
        printf("%d\n", dp[m]);
    }
    return 0;
}

Judge Method

雖然原題的 T$T$ 的範圍限制高達 100$100$，但請輸出一個 T=1$T=1$ 的測試資料，使得上述的程式碼會輸出錯的答案。

Sample Program

以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料。

#include <cstdio>
int main() {
    puts("1");
    puts("3 3");
    puts("1 2 3");
    return 0;
}