e928 - pB. 多項式相乘
題目描述
題目要求計算兩個一元多次多項式的乘積。輸入包含兩個多項式的係數和最高冪次，輸出乘積多項式的最高冪次和係數。
解題思路
此題使用模擬多項式乘法的基本方法。對於兩個多項式 a 和 b，其乘積 c 的每一項係數等於 a 的每一項係數乘以 b 的每一項係數。具體來說，對於 a 的第 i 項和 b 的第 j 項，它們的乘積對應於 c 的第 (i+j) 項。程式碼中，使用兩個巢狀迴圈遍歷 a 和 b 的每一項，計算它們的乘積並累加到 c 的相應項中。最後，找到 c 的最高冪次，並輸出最高冪次和係數。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 和 m 分別是兩個多項式的最高冪次加一。
- 空間複雜度: O(n+m)，用於儲存兩個多項式和它們的乘積。
程式碼
#include <stdio.h>
int a[101],b[101],c,ans[201],d,amax,i,j;
int main(){
scanf("%d",&c);
for(i=c;i>=0;--i)
scanf("%d",&a[i]);
scanf("%d",&d);
for(j=d;j>=0;--j)
scanf("%d",&b[j]);
for(i=0;i<=c;++i)
for(j=0;j<=d;++j)
ans[i+j]+=a[i]*b[j];
for(i=200;i>=0;--i)
if(ans[i]){
printf("%d\n",i);
amax=i;
break;
}
for(i=amax;i>=0;--i)
printf("%d ",ans[i]);
}