OI練習題 式子 recursion

【問題描述】

動態規劃 DP 的實現形式之一是遞推，因此遞推在 oi 中十分重要。在某資訊學的分支學科中， LC 學會瞭如何求一階線性遞推數列。由於他現在正在學習主幹學科，因此希望知道求出 N 階線性遞推數列。為此，他瞭解到了以下的內容：

一個 N 階線性遞推式是這樣的式子：

也就是說，這個數列的每一項都是由他之前連續 N 項加權相加所得。其中還包括一個常數 an 。

例如，當 N=2 ， a0=a1=1 ， a2=0 時，這個式子就是我們熟悉的斐波那契數列。當然，作為這界條件， f0 、 f1…f n-1 都是已知的。

LC 對這如何去求這個式子一籌莫展，因此請你來幫助他。你的任務就是對於一個給定的 N 階線性遞推式，求出它的第 K 項是多少。

【輸入文件】

第一行兩個整數： N ， K ，其中 N 表示這個式子是 N 階線性遞推式， K 表示你需要求得那一項。

第二行有 N+1 個整數： A0,A1,… ， An ，表示這個遞推式的係數。

第三行有 N 個整數： F0 ， F1 ， …. ， Fn-1 ，表示數列的初始值。

【輸出文件】

只有一行，其中只有一個整數，表示這個數列第 K 項的值。由於資料較大，你只需輸出結果 mod 9973 的值。

NOIP1995 普及組 編碼問題 code

【問題描述】

設有一個數組 A ： ARRAY[0..N-1] OF INTEGER ；數組中存儲的元素為 0-N-1 之間的整數，且 A[I] ≠ A[J] ( 當 I ≠ J) 時。

例如： N=6 時，有：（ 4 ， 3 ， 0 ， 5 ， 1 ， 2 ）

此時，數組 A 的編碼定義如下：

A[0] 的編碼為 0 ：

A[I] 的編碼為：在 A[0] ， A[1] ，…… A[I-1] 中比 A[I] 的值小的元素的個數（ I=1 ， 2 ，…… N-1 ）

所以上面數組 A 的編碼為 :B=(0,0,0,3,1,2)

程序要求解決以下問題

① 給出數組 A 後，求出其編碼；

② 給出數組 A 的編碼後，求出 A 的原資料。

[遞推]CTSC1999 月亮之眼 Moon 解題報告

         IOI1999 中國國家隊選拔賽 月亮之眼
【問題描述】
    吉兒是一家古董店的老闆娘，由於她經營有道，小店開得紅紅火火。昨天，吉兒無意之中得到了散落民間幾百年的珍寶—月亮之眼。吉兒深知“月亮之眼”價值連城：它是由許多珍珠相連而成的，工匠們用金線連接珍珠，每根金線連接兩個珍珠；同時又對每根金線染上兩種顏色，一半染成銀白色，一半染成黛黑色。由于吉兒自小熟讀古籍，所以還曉得“月亮之眼”的神祕傳說：“月亮之眼”原是一個古代寺廟的寶物，原本是掛在佛堂的一根頂樑柱上的，整個寶物垂直懸掛，所有珍珠排成一線，且都鑲嵌在柱子裡，而每一根金線又都是繃緊的，並且金線的銀白色一端始終在黛黑色一端的上方；然而，在一個月圓之夜，“月亮之眼”突然從柱裡飛出，掉落下來，寶物本身完好無損，只是僧侶們再也無法以原樣把“月亮之眼”嵌入柱子中了。吉兒望著這個神祕的寶物，回憶著童年讀到的傳說，頓時萌發出恢復“月亮之眼”的衝動，但是擺弄了幾天依舊沒有成功。

現在，要麻煩您來幫助吉兒完成這項使命。

您要設計一個程序，對於給定的“月亮之眼”進行周密分析，然後給出這串寶物幾百年前嵌在佛堂頂樑柱上的排列模樣。給定的“月亮之眼”有N個珍珠和P根金線，所有珍珠按一定順序有了一個序號：1、2…、N。