企业官网建设流程全解析

✅ PAT 甲级题目讲解：1009《Product of Polynomials》

📝摘要：本文讲解 PAT 甲级 1009《Product of Polynomials》的完整解法。核心思路是使用数组作为指数映射表，通过双层循环模拟两个稀疏多项式的逐项相乘与合并同类项，时间复杂度O(k1×k2)O(k_1 \times k_2)O(k1​×k2​)。文中给出了从输入、计算到格式化输出的分步代码，并整理了常见错误（小数精度、空格控制、忘用+=累加等）与思维拓展方向。

🧩 题目简介

本题要求实现两个多项式的乘法。

即给定两个稀疏多项式A(x)A(x)A(x)和B(x)B(x)B(x)，求出它们的乘积多项式C(x)=A(x)×B(x)C(x) = A(x) \times B(x)C(x)=A(x)×B(x)。

最后输出非零项（指数从大到小排列，保留一位小数）。

🧪 样例分析

输入样例：

2 1 2.4 0 3.2 2 2 1.5 1 0.5

两个多项式分别为：

• A(x)=2.4x1+3.2x0A(x) = 2.4x^1 + 3.2x^0A(x)=2.4x1+3.2x0
• B(x)=1.5x2+0.5x1B(x) = 1.5x^2 + 0.5x^1B(x)=1.5x2+0.5x1

手动展开乘积：

C(x)=(2.4x1+3.2)×(1.5x2+0.5x1)=2.4x1×1.5x2+2.4x1×0.5x1+3.2x0×1.5x2+3.2x0×0.5x1=3.6x3+1.2x2+4.8x2+1.6x1 \begin{aligned} C(x) &= (2.4x^1 + 3.2) \times (1.5x^2 + 0.5x^1) \\ &= 2.4x^1 \times 1.5x^2 + 2.4x^1 \times 0.5x^1 + 3.2x^0 \times 1.5x^2 + 3.2x^0 \times 0.5x^1 \\ &= 3.6x^3 + 1.2x^2 + 4.8x^2 + 1.6x^1 \end{aligned}C(x)​=(2.4x1+3.2)×(1.5x2+0.5x1)=2.4x1×1.5x2+2.4x1×0.5x1+3.2x0×1.5x2+3.2x0×0.5x1=3.6x3+1.2x2+4.8x2+1.6x1​

合并同类项后：

• C(x)=3.6x3+6.0x2+1.6x1C(x) = 3.6x^3 + 6.0x^2 + 1.6x^1C(x)=3.6x3+6.0x2+1.6x1

输出为：

3 3 3.6 2 6.0 1 1.6

🔍 解题思路

本题的本质是稀疏多项式的乘法展开 + 合并同类项 + 格式控制输出。
多项式乘法的核心是逐项相乘：

A(x)=∑i=1k1aixni,B(x)=∑j=1k2bjxmj A(x) = \sum_{i=1}^{k_1} a_i x^{n_i}, \quad B(x) = \sum_{j=1}^{k_2} b_j x^{m_j}A(x)=i=1∑k1​​ai​xni​,B(x)=j=1∑k2​​bj​xmj​

则：

C(x)=A(x)×B(x)=∑i=1k1∑j=1k2aibjxni+mj C(x) = A(x) \times B(x) = \sum_{i=1}^{k_1} \sum_{j=1}^{k_2} a_i b_j x^{n_i + m_j}C(x)=A(x)×B(x)=i=1∑k1​​j=1∑k2​​ai​bj​xni​+mj​

📎 变量说明表格

✅ Step 1：输入两个稀疏多项式

cin>>k1;for(inti=1;i<=k1;i++){cin>>n[i]>>a[i];// A 的指数和系数}cin>>k2;for(inti=1;i<=k2;i++){cin>>m[i]>>b[i];// B 的指数和系数}

✅ Step 2：逐项相乘，累加结果

模拟C(x)=A(x)×B(x)C(x) = A(x) \times B(x)C(x)=A(x)×B(x)的计算过程，数学公式为：

C(x)=A(x)×B(x)=∑i=1k1∑j=1k2aibjxni+mj C(x) = A(x) \times B(x) = \sum_{i=1}^{k_1} \sum_{j=1}^{k_2} a_i b_j x^{n_i + m_j}C(x)=A(x)×B(x)=i=1∑k1​​j=1∑k2​​ai​bj​xni​+mj​

代码实现使用双层循环逐项相乘，累加结果：

for(inti=1;i<=k1;i++){// A 有 k1 项for(intj=1;j<=k2;j++){// B 有 k2 项intt=n[i]+m[j];// 新项指数c[t]+=a[i]*b[j];// 合并同类项maxn=max(maxn,t);// 更新最大指数}}

✅ Step 3：统计非零项数 + 按指数从大到小输出

for(inti=0;i<=maxn;i++){if(c[i])s++;// 非零项统计}printf("%d",s);for(inti=maxn;i>=0;i--){if(c[i]){// 该项非 0printf(" %d %.1lf",i,c[i]);// 注意先输出空格}}

✅ 完整代码

#include<bits/stdc++.h>usingnamespacestd;intk1,k2,n[15],m[15],maxn,s;doublea[15],b[15],c[2005];intmain(){cin>>k1;for(inti=1;i<=k1;i++){cin>>n[i]>>a[i];}cin>>k2;for(inti=1;i<=k2;i++){cin>>m[i]>>b[i];}for(inti=1;i<=k1;i++){for(intj=1;j<=k2;j++){intt=n[i]+m[j];c[t]+=a[i]*b[j];maxn=max(maxn,t);}}for(inti=0;i<=maxn;i++){if(c[i])s++;}printf("%d",s);for(inti=maxn;i>=0;i--){if(c[i]){printf(" %d %.1lf",i,c[i]);}}return0;}

🚧 常见错误提醒

✅ 总结归纳

• 本题为稀疏多项式乘法模拟；
• 建议使用数组作为指数映射表c[i]，空间换时间；
• 注意控制：
  • 合并同类项；
  • 按指数从大到小输出；
  • 浮点数格式%.1lf；
  • 严格空格输出。

时间复杂度约为O(k1×k2)O(k_1 \times k_2)O(k1​×k2​)，完全可接受。

🧠 思维拓展

• 如果改成多项式求和，只需将对应c[i]做加法；
• 更复杂情形可引入结构体表示项，并排序；
• 这类题是数据结构课程中“稀疏数组”模型的重要应用。