我的作法是一個根一個根讀進來,再加上滾動數組來做(因為不需要知道更早之前的結果,只要關注最近的兩個就好,也可以不用啦)
一個根一個根讀進來的話,就可以看成是一個 (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; } }