ZeroJudge 解題筆記：s573. 多項式 - 判斷正負

作者：王一哲
日期：2026年8月9日


ZeroJudge 題目連結：s573. 多項式 - 判斷正負

解題想法

這題與 s562. 多項式 - 湊出 a_n 幾乎一樣。題目定義 $$ (1 - a)(1 - b)(1 - c)(1 - d) \dots = 1 - a - b + ab - c + ac + bc - abc - d + \dots $$ 測資第一行為 $t$，代表接下來有 $t$ 行數字 $n$，要回傳第 $n$ 項的正負號。實際上這題考的是二進位，先計算 $n$ 的二進位制之中有幾個 $1$，如果。$1$ 的數量為偶數輸出 $+$，數量為奇數輸出 $-$。

Python 程式碼

解題時間約為 0.2 s，使用記憶體約為 8.4 MB。

def solve():
    import sys

    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())
        b = n.bit_count()
        if b % 2 == 0:
            sys.stdout.write("+\n")
        else:
            sys.stdout.write("-\n")

if __name__ == "__main__":
    solve()

C++ 程式碼

解題時間約為 0.2 s，使用記憶體約為 1.4 MB。

#include <cstdio>

int main() {
    int t, n, b;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        scanf("%d", &n);
        b = __builtin_popcount(n);
        if ((b&1) == 0) puts("+");
        else puts("-");
    }
    return 0;
}

解題時間約為 0.1 s，使用記憶體約為 3.2 MB。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t, n, b;
    cin >> t;
    for(int i = 0; i < t; i++) {
        cin >> n;
        b = __builtin_popcount(n);
        cout << ((b&1) == 0 ? "+\n" : "-\n");
    }
    return 0;
}

C 語言程式碼

解題時間約為 0.2 s，使用記憶體約為 1.4 MB。

#include <stdio.h>

int main() {
    int t, n, b;
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        scanf("%d", &n);
        b = __builtin_popcount(n);
        if ((b&1) == 0) puts("+");
        else puts("-");
    }
    return 0;
}