方程

题目

什么是多项式？我数学不好不太会。

还是数学课，小J和小R在数学课上遇到了 (x+y)²=x²+2xy+y²，小J继续推导 (x+y)³=x³+3x²y+3y²x+y³。

小J和小R把其中的系数拿出来排成了一个序列，发现是1 2 1和1 3 3 1。

小R："你可以告诉我如果是 (x+y)ⁿ 他们的系数会是什么样子吗？"

小J："比起问我不如问问正在做题的同学们。"

下面交给你了！

小J和小R想知道多项式 (x+y)ⁿ 分解后每一项的系数分别是多少，现在请你来帮助他们！

输入：第一行1个整数 n。
输出：依次输出 (x+y)ⁿ 每一项的系数。（由于数据可能较大，答案请取模 998244353 输出）

样例1：

2

1 2 1

样例2：

3

1 3 3 1

提示：对于 30% 的数据，保证 n≤100。对于 60% 的数据，保证 n≤1000。对于 100% 的数据，保证 n≤10000。

思路

(x+y)ⁿ 展开后第 k 项的系数是二项式系数 C(n,k)，恰好对应杨辉三角第 n 行。用一维 DP 滚动更新：只保留一行，每轮从右往左推，c[d] = c[d] + c[d-1]，避免用到已更新的值。需要注意三个边界：

• 内层从右往左：若从左往右，c[d-1] 已被本轮更新，计算结果错误。
• 内层起点是 c+1，不是 c：第 c 轮新增的最右边那个 1 在位置 c+1，起点是 c 会漏掉它。
• 输出循环到 e<=n，不是 e<n：(x+y)ⁿ 有 n+1 项（从 C(n,0) 到 C(n,n)），少一位会丢掉最后的 1。

#include<bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

int main(){
    int n;
    cin>>n;

    vector<long long> yh_triangle(n+1,0);
    yh_triangle[0]=1;
    for(int c=0;c<n;c++){
        for(int d=c+1;d>0;d--){
            yh_triangle[d]=(yh_triangle[d]+yh_triangle[d-1])%MOD;
        }
    }

    for(int e=0;e<=n;e++){
        cout<<yh_triangle[e]<<" ";
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(n²)，双层循环各跑 n 次
• 空间复杂度：O(n)，只用一维数组滚动更新

← 返回菜鸟的coding