作者：王一哲
日期：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()
