以下是不重要的故事
超級貓貓 Poo 是一隻喜歡研究各種奇怪理論的貓貓🐱✨。其中信號與系統,就是 Poo 非常喜歡的一門理論。
信號 signal ,是傳遞有關一些現象的行為或屬性的資訊的函數 (cite from wiki)。而這門學問,旨在研究針對一個系統 (system) ,輸入信號 (input signal) 後,其輸出信號 (output signal) 會具有什麼性質,也關心這個系統有什麼性質,等等。
Poo 某天學習到了一個系統,針對輸入的離散信號 $x[n]$,輸出的信號會是 $y[n]=x[0]+x[1]+x[2]+...+x[n]$。
Note: 離散信號,可以簡單想像成,從整數映射到實數的函數 $x$: $\mathbb{Z} \to \mathbb{R}$。比方說,$x[n]=n$ 代表 $x[0]=0$, $x[1] = 1$, $x[2]=2$ 的線性函數。
一個系統,可以簡單想像成,會把輸入函數 $x$ 轉換成另外一個輸出函數 $y$ 的機器。比方說 $y[n]=x[n]+1$ 代表這個系統,會讓輸出的函數 $y$ 在每個不同的整數點 $n$ ,和輸入函數 $x$ 呈現的關係是 $y[n]=x[n]+1$。若輸入 $x[n]=n$ 這個信號,則會得到 $y[n]=x[n]+1=n+1$ 這個平移過的線性函數。
這個系統的輸入輸出對應是,在第 $n$ 個時刻的輸出,是所有過去輸入到第 $n$ 個時刻的輸入的數值總和。比方說,$x[0]=1$, $x[2]=10$, $x[3]=1$,則輸出 $y[0]=1$, $y[1]=11$, $y[2]=12$。
這樣看似簡單的系統,其實就是一個最基礎的 LPF (Low Pass Filter) (忽略低頻的係數的成長)。也就是可以過濾掉一部分信號高頻成分,留下低頻成分的一個系統。
Frequency vs. Magnitude of the frequency response of the system
LPF 在非常多地方都有應用,包含: 音頻處理,消除聲音中的高頻噪音;影像處理,去除影像中的噪點;在機器學習中,處理數據的雜訊。如此複雜的應用,居然可以透過這樣簡易的系統進行初步的實現,著實令人驚豔。
Poo 讀完這段理論後覺得實在太有趣了,想要實際實作看看。但 Poo 只是一隻貓啊 !!!!!! 請你幫他實作這樣的系統 !
第一行會有兩個數字 $L$, $m$ ,$L$ 表示輸入信號的長度,$m$ 表示要詢問幾個不同時間點的輸出。
接下來 $L$ 行,代表輸入信號實際的數值。
第 $2$ 行,代表的是 $x[0]$ 的數值,
第 $i$ 行,代表的是 $x[i-2]$ 的數值。
接下來 $m$ 行,代表要詢問的輸出時間點,
對於每一行的數字 $v$,你必須輸出 $y[v]$ 的數值。
比方說:
3 2
1
2
3
0
2
代表信號長度為 $3$
$x[0] = 1$
$x[1] = 2$
$x[2] = 3$
要詢問
$y[0]=?$
$y[2]=?$
保證 $1\leq L \leq 1e4$,$ 1 \leq m \leq L $,$ -100 \leq x[i] \leq 100$。
請將要求的每個時間點輸出結果逐行輸出
以同一個例子而言,請輸出
1
6
因為:
$y[0]=x[0]=1$
$y[2]=x[0]+x[1]+x[2]=1+2+3=6$
No. | Testdata Range | Score |
---|---|---|
1 | 0~9 | 100 |