#30478: 解題報告


dfd8282@gmail.com (fishhh)

學校 : 嘉義市私立嘉華高級中學
編號 : 99760
來源 : [140.116.247.244]
最後登入時間 :
2024-04-28 14:32:43
d437. 10326 - The Polynomial Equation -- UVa10326 | From: [36.236.42.248] | 發表日期 : 2022-05-24 00:19

我的作法是一個根一個根讀進來,再加上滾動數組來做(因為不需要知道更早之前的結果,只要關注最近的兩個就好,也可以不用啦)

一個根一個根讀進來的話,就可以看成是一個 (x-r) 與前面輸入進來的乘積相乘。也就是只要處裡兩項與多項的乘法就好,不需要處裡多項乘多項的狀況。

乘法的部分,就知道兩件事就好

  1. 將所有目前的值,全部左移一位,然後把左移後的式子先設為新的式子 ex.( 3x^2+4x+99 變成 3x^3+4x^2+99x )
  2. 將上個規則算出來新式子每項的值加上 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;
            }
        }

 
ZeroJudge Forum