[NOIP2009-普及] 多项式输出

题目描述

给定一元 $n$ 次多项式降幂排列的 $n+1$ 个系数，按规则输出多项式：只保留非零项；首项正号省略、负号开头，其余项用 + / - 连接；高于 $0$ 次且系数绝对值为 $1$ 时省略系数；指数部分按次数输出 x^b、x 或空。

样例#1 输入 5 / 100 -1 1 -3 0 10，输出 100x^5-x^4+x^3-3x^2+10；样例#2 输入 3 / -50 0 0 1，输出 -50x^3+1。

数据范围： $0 \le n \le 100$ ，系数绝对值 $\le 100$ 。

思路

从高次到低次扫描系数， $0$ 则跳过；用 first 标记是否为首项非零项，就地决定符号、系数是否省略、幂次形式并直接输出。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 08:02
# update_at: 2026-10-02 08:02

import sys


def render(coeffs: list[int]) -> str:
    """把降幂排列的系数序列按题目格式渲染成多项式字符串。

    首项（最高次非零项）正号省略、负号直接作开头；其余非零项用 +/- 连接。
    高于 0 次且系数绝对值为 1 时省略系数 1；0 次项只输出系数。
    """
    out: list[str] = []
    for i, coeff in enumerate(coeffs):
        if not coeff:
            continue                                      # 只输出系数不为 0 的项
        deg = len(coeffs) - 1 - i                          # 本项次数：序列首项即最高次
        sign = "-" if coeff < 0 else "+" if out else ""    # 首项正号不输出
        head = "" if abs(coeff) == 1 and deg else str(abs(coeff))  # 省略的只是系数 1
        power = f"x^{deg}" if deg > 1 else "x" if deg else ""      # 指数部分三种形式
        out.append(sign + head + power)
    return "".join(out)


def solve() -> None:
    data = iter(map(int, sys.stdin.read().split()))
    n = next(data)                                     # 多项式次数
    coeffs = [next(data) for _ in range(n + 1)]        # 降幂排列的 n+1 个系数
    print(render(coeffs))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:15
 * update_at: 2026-10-06 14:15
 */

#include <iostream>
using namespace std;

typedef long long ll;
const int MAXN = 105; // n <= 100

ll a[MAXN]; // 降幂排列的系数，a[i] 对应 x^(n-i)
int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i <= n; i++) cin >> a[i];

    bool first = true; // 是否还未输出任何非零项
    for (int i = 0; i <= n; i++) {
        ll coeff = a[i];
        if (coeff == 0) continue; // 只输出非零项

        int deg = n - i; // 当前项次数

        // 符号：首项正号省略，其余按正负输出 + 或 -
        if (first) {
            if (coeff < 0) cout << '-';
        } else {
            cout << (coeff < 0 ? '-' : '+');
        }

        // 系数：高于 0 次且绝对值为 1 时省略
        ll aval = coeff < 0 ? -coeff : coeff;
        if (!(aval == 1 && deg > 0)) cout << aval;

        // 幂次：>1 输出 x^b，=1 输出 x，=0 不输出
        if (deg > 1) cout << 'x' << '^' << deg;
        else if (deg == 1) cout << 'x';

        first = false;
    }

    cout << '\n';
    return 0;
}

[NOIP2009-普及] 多项式输出

目录

题目描述

思路

参考代码