c629. 魔法開端 - 高中生程式解題系統

內容

據說在成為大魔法師之前， $A w$ 只是位計程車司機。日復一日的工作使他困惑 ── 十餘年來為了接送旅客往返四方，自己人生的目的地又在哪兒呢？

這天，帶著迷惘上路， $A w$ 不知不覺來到一處岩壁，剎那間天搖地動，石塊滾滾而下。 $A w$ 立即奔出車外，幸運地逃過一劫。回頭，縱使塵土飛揚，卻依稀可見岩壁上一道裂縫正微微透著奇異光芒 ── 那是個洞窟的入口，他決定前去一探究竟。

貓有九命，然而好奇心能殺死一隻貓。入口在 $A w$ 踏進洞窟的同時闔上並冒出烈燄，逐漸朝他延燒，而洞窟另一頭有扇雕紋精美的木門，上面鋪著藍與黑的圖案。木門似乎是唯一出路，只不過門把轉也轉不動。此時， $A w$ 的腦中湧現無數自己從未接觸過的知識：藍黑色圖案是基礎魔法咒文，可分別以 $n * n$ 的特殊方陣 $A, B$ 分析。

基礎魔法的方陣 $A, B$ 必能以特定的 $s, a, c$ 生成。首先將 $s$ 填入左上角，接著逐次向右移動一格（超出邊界時移到下一列最左邊的格子），並填入 $a * (上個格子的數值) + c$ 。

咒文疊加後能交織成更強大的複合魔法，其方陣即為各個基礎魔法方陣的乘積，例如木門上的魔法可寫作 $C = A * B$ ，其中 $C_{i j} = \sum_{k = 0}^{n - 1} A_{i k} * B_{k j}$ ，注意到這裡方陣的行列編號使用 $0 \sim n - 1$ 。
在火焰吞噬整個洞窟以前， $A w$ 必須求得若干個 $C_{i j}$ 的數值好讓他攻擊魔法的弱點，為了確定自己計算無誤，他透過某種方式向你求助，希望你告訴他 $C_{i j}$ 除以 $10^{9} + 7$ 的餘數。

輸入說明

首行有兩個正整數 $n, q (1 \leq n \leq 10^{9}, 1 \leq q \leq 500000)$ 代表方陣大小及詢問數量。

第二行為用以生成方陣 $A$ 和 $B$ 的整數 $s_{A}, a_{A}, c_{A}, s_{B}, a_{B}, c_{B} (0 \leq s, a, c < 10^{9} + 7)$ 。

接下來 $q$ 行分別有兩個整數 $i, j (0 \leq i, j < n)$ 代表詢問位置。

輸出說明

對於每次詢問，輸出 $C_{i j} % (10^{9} + 7)$ 的值於一行。

範例輸入 #1

3 9
1 1 2 10 0 0
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

範例輸出 #1

測資資訊：

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

提示：

範例中 $A = [\begin{matrix} 1 & 3 & 5 \\ 7 & 9 & 11 \\ 13 & 15 & 17 \end{matrix}], B = [\begin{matrix} 10 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}], C = [\begin{matrix} 10 & 0 & 0 \\ 70 & 0 & 0 \\ 130 & 0 & 0 \end{matrix}]$ 。

測資點 $0 \sim 1 (6 %)$ ， $n \leq 500, q \leq 30000$ 。

測資點 $2 \sim 3 (16 %)$ ， $n \leq 2000, q \leq 30000$ 。

測資點 $4 (14 %)$ ， $n \leq 2500000, s_{B} = c_{B} 且 a_{B} = 0$ 。

測資點 $5 \sim 7 (24 %)$ ， $n \leq 2500000$ 。

測資點 $8 \sim 11 (40 %)$ ，無特殊限制。

標籤:

出處:

[管理者： icube (!@#$%^&*()_...) ]

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