a645. C. 防禦工事 - 旦旦解題農場

內容

調查軍團根據地形判斷敵軍大概率會從某段海岸來搶灘，因此想在此段海岸線上布置$N$個長度為$R_i$的相異陷阱，為了簡化問題，我們假設海岸線長度為$0\sim L$，且陷阱的左右兩端點都須在整數點上，並且一個陷阱不能被另一陷阱覆蓋。

由於某些因素，每天會有其中一個陷阱的長度發生變化，已知變化後的陷阱長度不會為0，且變化量$|K|$小於20，試求每天變化後布置的可能數 (由於可能數過大請同餘 $1000000007$)。

輸入說明

第1列會有兩數$N, L$，分別代表陷阱數及海岸線長度

第2列會有$N$個數$R_i$，依序代表陷阱長度

第3列會有一數$T$代表接下來的天數

接下來$T$列，每列會有兩數$idx, K$，代表被改變的陷阱編號及改變量。

對於100%的測資 $1 \leq N, \; T \leq 10^5$, $1 \leq L \leq 10^9$, $1 \leq R_i \leq 10^4$

輸出說明

請先輸出尚未變化前布置的可能數。

接著輸出$T$列，每天經過變化後布置的可能數。

範例輸入

範例輸出

2
6

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (10%): 1.0s , <10M
公開測資點#1 (10%): 1.0s , <10M
公開測資點#2 (10%): 1.0s , <10M
公開測資點#3 (10%): 1.0s , <10M
公開測資點#4 (10%): 1.0s , <10M
公開測資點#5 (10%): 1.0s , <10M
公開測資點#6 (10%): 1.0s , <10M
公開測資點#7 (10%): 1.0s , <10M
公開測資點#8 (10%): 1.0s , <10M
公開測資點#9 (10%): 1.0s , <10M

提示：

範測中尚未變化前的可能情形為

1 2-2 及 2-2 1

經過第1天的變化後的可能情形為

1 2 X, 1 X 2, X 1 2
2 1 X, 2 X 1, X 2 1

標籤:

出處:

DDJ Regular Contest Round#8 [管理者：

fdhs108_38002 (NULL)

]

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