我的作法是一個根一個根讀進來,再加上滾動數組來做(因為不需要知道更早之前的結果,只要關注最近的兩個就好,也可以不用啦)
一個根一個根讀進來的話,就可以看成是一個 (x-r) 與前面輸入進來的乘積相乘。也就是只要處裡兩項與多項的乘法就好,不需要處裡多項乘多項的狀況。
乘法的部分,就知道兩件事就好
其實這題整體是很漂亮的!!
以下為部分code
int roll[52][2]={},k;
cin>>k;
k*=-1;
roll[0][0]=k,roll[1][0]=1;
for(int i=1;i<n;i++){
cin>>k;
k*=-1;
int now=i%2,inor=1-i%2;
roll[0][now]=0;
for(int ix=1;ix<=i+1;ix++){
roll[ix][now]=roll[ix-1][inor];
}
for(int ix=0;ix<=i;ix++){
roll[ix][now]+=roll[ix][inor]*k;
}
}