i370. 劍術不見林 - Extreme
標籤 :
通過比率 : 2人/7人 ( 29% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-10 21:57

內容

尤吉歐在 Underworld 砍倒惡魔之樹之後,下定決心和桐人一樣成為一名劍士,於是他向桐人學習「艾恩葛朗特流」。

今天學習的內容是「水平方陣斬」,於是桐人帶著尤吉歐來到了盧利特村旁邊的森林練習,為了方便訓練,桐人把森林裡的樹幾乎砍光只剩下四棵樹,其中這四棵樹會形成一個長方形以利於水平方陣斬的練習。每棵樹都有一個天命,每施放一次劍技這四棵樹就會減少 $1$ 單位的天命,天命一旦耗盡,這棵樹就會消失。

現在給你一個 $n\times m$ 大小的森林裡面有 $n\times m$ 棵樹,還有每棵樹的天命,要問你尤吉歐最多可以練習幾次水平方陣斬。

輸入說明

第一行輸入兩個用空白隔開的正整數 $n$ 和 $m$ ,代表森林的大小,第二行有三個整數 $D_{1,1},S,A,O$,代表位於 $(1,1)$ 的樹的天命還有三個常數,對於每一棵位於 $(i, j), (1\le i\le n, 1\le j\le m,i+j>2)$ 的樹 $D_{i,j}$,他的天命會是

$D_{i,j} =  ((((pre_{i,j} \times S) \oplus A) + O)\oplus 48763)\times 1016 \mod 1000000000 + 1$

$pre_{i,j} = \left\{\begin{matrix}D_{i,j-1}, j>1\\D_{i-1,m}, j=1\end{matrix}\right.$

其中 $\oplus$ 指的是 bitwise xor

 

測資限制

$1\le n, m\le 4000$

$1\le D_{i,j} \le 10^9$

$1\le S,A,O\le 10^9$

 

輸出說明

輸出一個整數,代表尤吉歐最多可以練習幾次水平方陣斬。

範例輸入 #1
3 3
48763 10 16 74
範例輸出 #1
356781705
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1K
不公開 測資點#6 (10%): 1.0s , <1K
不公開 測資點#7 (10%): 1.0s , <1K
不公開 測資點#8 (10%): 1.0s , <1K
不公開 測資點#9 (10%): 1.0s , <1K
提示 :

禁忌目錄中有規定:把樹砍掉後,每個橫列跟直排的樹的數量都要是偶數個。

使用正確的時間複雜度才能通過。

生成森林的 code

第一筆範例測資中的森林長這樣

48763 520016233 390438025
885338249 867977 843246729
405124745 100332681 356781705

標籤:
出處:
[管理者: Easonsfriend (去寫./Problems?ow...) ]

本題狀況 本題討論 排行

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