ZeroJudge 解題筆記：d224. 11296 - Counting Solutions to an Integral Equation

作者：王一哲
日期：2026年5月12日


ZeroJudge 題目連結：d224. 11296 - Counting Solutions to an Integral Equation

解題想法

這題可以用公式解或是動態規畫。 $$ x + 2y + 2z = n ~\Rightarrow~ x = n - 2(y + z) = n - 2k $$ 因為題目要求 $x, y, z$ 為 0 或正整數，因此 $$ y + z = k ~\Rightarrow~ 0 \leq k \leq \left \lfloor \frac{n}{2} \right \rfloor = m $$ 符合條件的 $(y, z)$ 為 $(0, k), (1, k-1), \dots, (k, 0)$，共有 $k + 1$ 組，因此所有的解數量為 $$ \sum_{k=0}^{m} (k+1) = 0 + 1 + 2 + \dots + (m+1) = \frac{(m+1)(m+2)}{2} $$ 如果用 $dp[i]$ 代表 $x + 2y + 2z = i$ 時的解數量，起始條件為 $dp[0] = 1$。$x = 0, 1, 2, \dots, n$，當 $x$ 加 1 時，解的數量會更新為 $$ dp[i] = dp[i] + dp[i-1] $$ $y, z = 0, 1, 2, \dots, \left \lfloor \frac{n}{2} \right \rfloor$，則 $y$ 或 $z$ 加 1 時，解的數量會更新為 $$ dp[i] = dp[i] + dp[i-2] $$

Python 程式碼

公式解，使用時間約為 40 ms，記憶體約為 11.4 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        m = n//2
        result.append(f"{(m+1)*(m+2)//2:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

動態規畫，使用時間約為 0.4 s，記憶體約為 63.6 MB，通過測試。

def solve():
    import sys

    maxn = 1000000
    dp = [0]*(maxn+1)
    dp[0] = 1  # i = 0，1 組解
    for i in range(1, maxn+1):  # 加入 x
        dp[i] += dp[i-1]
    for i in range(2, maxn+1):  # 加入 y
        dp[i] += dp[i-2]
    for i in range(2, maxn+1):  # 加入 z
        dp[i] += dp[i-2]

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        result.append(f"{dp[n]:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

公式解，使用時間約為 11 ms，記憶體約為 1.5 MB，通過測試。

#include <cstdio>
typedef long long LL;

int main() {
    LL n;
    while(scanf("%lld", &n) != EOF) {
        LL m = n/2;
        printf("%lld\n", (m+1) * (m+2) / 2);
    }
    return 0;
}

動態規畫，使用時間約為 15 ms，記憶體約為 9.1 MB，通過測試。

#include <cstdio>
typedef long long LL;

LL dp[1000000];

int main() {
    dp[0] = 1;
    for(int i=1; i<=1000000; i++) dp[i] += dp[i-1];
    for(int i=2; i<=1000000; i++) dp[i] += dp[i-2];
    for(int i=2; i<=1000000; i++) dp[i] += dp[i-2];
    
    LL n;
    while(scanf("%lld", &n) != EOF) {
        printf("%lld\n", dp[n]);
    }
    return 0;
}