跳至主要内容

Two Sets II

題目​

給一個數 nn (1≤n≤500)(1\leq n\leq500) ，問你有幾種方法將 1∼n1\sim n 的數分成兩堆，且兩堆總和相同，由於答案可能很大，請對 109+710^9+7 取餘數。

輸入​

共一個數 nn 。

輸出​

共一個數，代表有多少種方法。

範例測資​

Input:
7

Output:
4

想法​

先簡化一下題目，我們要用一些數湊出某個總和，而這個總和會是 n(n+1)4\frac{n(n+1)}{4} ，如果他不是整數，代表兩堆湊不出相同的值，答案是 0 。

否則，問題變成有 1∼n1\sim n 的數各一個，問有幾種做法能湊出 n(n+1)4\frac{n(n+1)}{4} 。 首先可以枚舉所有拿法，最簡單就是每個數選擇拿或不拿，但是這樣的時間複雜度是 O(2n)O(2^n) 。

但是這樣太慢了，我們又希望能夠更快，就代表我們需要改變枚舉的方法。

現在，我們考慮某一個物品、要不要放，得到的結果是特定總和的答案。 那我們可以調換一下變因，改成考慮某個物品、以及現在的總和，聽起來可能很抽象，但這件事就像是值域二分搜，換個角度看會有完全不同的複雜度。

假設 dpn,Wdp_{n,W} 代表的是選擇 1∼n1\sim n 間的數，重量恰好為 WW 的選擇方法，也就是我們要的答案。 可知 dpi,W={i==Wif i=0dpi−1,W+dpi−1,W−ielsedp_{i,W}=\left\{\begin{aligned}&i==W&\text{if }i=0\\&dp_{i-1,W}+dp_{i-1,W-i}&\text{else}\end{aligned}\right. ，也就是不取這個數的方法數，和取了這個數之後的方法數的總和就是答案，因此這是二維 dp ，並且由於他是考慮一個數可以選或不選，用枚舉值域的方式降低複雜度，所以是時間複雜度 O(nW)O(nW) 的 01 背包。

但其實，空間和時間上都能再優化，考慮剛剛的轉移式，會發現現在會用到的只有上一個物品的狀態，可以用滾動陣列做，附在範例程式碼二。 再仔細觀察，會用到的只有總和比現在小的狀態，因此從總和大的往小的做，就可以壓在一條陣列裡，配合接下來的時間優化一起附在範例程式碼三。

時間上，不需要跑過整個值域，假設現在正在選擇 ii ，只要考慮到 1∼i−11\sim i-1 的總和，也就是 0∼i(i−1)20\sim \frac{i(i-1)}{2}，最終的總複雜度是 O(∑i=1ni(i−1)2=n(n+1)(n−1)6)O(\sum_{i=1}^n\frac{i(i-1)}{2}=\frac{n(n+1)(n-1)}{6}) ，而原本的 O(nW=nn(n+1)4)O(nW=n\frac{n(n+1)}{4}) 略大一點，不過這題不卡常數，三個版本都能過，但類似的觀察有時候會有神奇的效果，甚至可能降低複雜度，像是均攤分析、離散化、或 dp 優化，總物品有限所以複雜度並沒有想像中的高。

這題還有一個特別的地方，這樣 dp 算出來的答案是所有總和為 WW 的方法數，但本題把左右兩堆交換視為一樣的，所以答案要除以二，而因為要對 109+710^9+7 取餘數，最終的答案應該是一個整數才對，若答案是奇數就會有問題，因此在取模的情況下，除法的定義變得有些不同，我們可以將 12\frac12 表示為 2−12^{-1} ，他會滿足 2×2−1≡1(mod109+7)2\times2^{-1}\equiv1\pmod{10^9+7} ，而費馬小定理告訴我們當 pp 是質數時， ap≡a(modp),ap−1≡1(modp),ap−2≡a−1(modp)a^p\equiv a\pmod p, a^{p-1}\equiv1\pmod p, a^{p-2}\equiv a^{-1}\pmod p ，而這樣的 a−1a^{-1} 便是乘法中的反元素，被我們簡稱為模反元素，可以透過快速冪算出答案，附在範例程式碼一。

費馬小定理限定在對質數取模的情況，更強的定理是歐拉定理 aφ(n)≡1(modn)a^{\varphi(n)\equiv1\pmod n} 其中 a,na,n 是任意整數， φ(n)\varphi(n) 代表 1∼n−11\sim n-1 中有多少數和 nn 互值，若 nn 是質數，便退化成費馬小定理。

而解決除以二的另外一種做法，便是讓狀況變成一半，最簡單的方式就是把任意一個數固定選在左半或右半，出於方便性，我們可以選擇 nn 固定在另一半，也就是考慮 1∼n−11\sim n-1 中總和為 WW 的狀況即可，附在範例程式碼二和三。

範例程式碼​

為了避免溢位，要使用 long long 並對 109+710^9+7 取餘數。

C++ 範例一
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL dp[505][130000];
int main() {
    int n, W, i = 1, j;
    cin >> n;
    W = n * (n + 1) / 2;
    if(W & 1) {
        cout << 0;
        return 0;
    }
    for(W /= 2, dp[0][0] = 1; i <= n; ++i) {
    	for(j = 0; j <= W; ++j) {
    		dp[i][j] = dp[i-1][j];
    		if(j >= i) {
    		    
                dp[i][j] += dp[i - 1][j - i];
                dp[i][j] %= 1000000007;
            }
    	}
    }
    cout << dp[n][W] * 500000004 % 1000000007;
}
C++ 範例二
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL dp[2][130000] = {1};
int main() {
    int n, W, i = 1, j , idx = 0;
    cin >> n;
    W = n * (n + 1) / 2;
    if(W & 1) {
        cout << 0;
        return 0;
    }
    for(W /= 2; i < n; idx ^= 1, ++i) {
    	for(j = 0; j <= W; ++j) {
    		dp[idx ^ 1][j] = dp[idx][j];
    		if(j >= i) {
                dp[idx ^ 1][j] += dp[idx][j - i];
                dp[idx ^ 1][j] %= 1000000007;
            }
    	}
    }
    cout << dp[idx][W];
}
C++ 範例三
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL dp[130000] = {1};
int main() {
    int n, W, i = 1, j;
    cin >> n;
    W = n * (n + 1) / 2;
    if(W & 1) {
        cout << 0;
        return 0;
    }
    for(W /= 2; i < n; ++i) {
    	for(j = i * (i + 1) / 2; j >= i; --j) {
            dp[j] += dp[j - i];
            dp[j] %= 1000000007;
        }
    }
    cout << dp[W];
}