c808: 皮皮爬樓梯
標籤 :
通過比率 : 100% (2 人 / 2 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2019-01-01 20:05

內容

傳說在午夜時分,________會出現一個___的樓梯,所有爬上_________________

充滿好奇心的皮皮決定來挑戰這個樓梯。

就如同大多數人,皮皮一步可以往上走一階或兩階樓梯,但是因為皮皮的腿很長,一次走三階也是可能的選擇。

現在請你計算皮皮從地面(第 0 階)走到第 k 階的方法有幾種。

噢對了,傳說後半段還有一件事情,如果踩到出現_______的樓梯,就會被_____________________

輸入說明

第一列有兩個正整數 N, M (N <= 10^9, M <= 100000),代表可以觀測到的樓梯有 N 階,且有 M 筆事件紀錄。

接下來 M 列,每列有兩個整數 x, k (1 <= k <= N),x = 1 代表第 k 階樓梯出現了_______, x = 0 則表示詢問皮皮走到第 k 階的方法數。

 

輸出說明

對於每次詢問,輸出皮皮走到第 k 階的方法數(在沒有被____________的情況下)對 1000000007 取模的結果。

範例輸入
10 7
0 1
0 2
0 3
0 10
1 3
0 2
0 4
範例輸出
1
2
4
274
2
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1M
公開 測資點#1 (20%): 2.0s , <1M
公開 測資點#2 (20%): 2.0s , <1M
公開 測資點#3 (20%): 2.0s , <10M
公開 測資點#4 (20%): 2.0s , <10M
提示 :

對於測資#00,N, M <= 1000。
對於測資#01,N, M <= 100000,詢問在所有的_______事件之後。
對於測資#02,N, M <= 100000。
對於測資#03、#04,無特殊限制。

標籤:
出處:
[編輯:
icube (常數爆炸)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」