c819: 皮皮與模逆元
標籤 :
通過比率 : 0% (0 人 / 0 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-11-23 19:44

內容

對於互質的正整數 $\color{black}{a, \space m}$ ,一定存在整數 $\color{black}{0 < b < m}$ 使得 $\color{black}{ab \equiv 1 \pmod{m}}$ ,此時就稱 $\color{black}{b}$ 是 $\color{black}{a}$ 對模數 $\color{black}{m}$ 的模逆元,也可記作 $\color{black}{a^{-1}}$。

皮皮現在有兩個整數序列 $\color{black}{A, B}$ (長度分別為 $\color{black}{s, t}$) 和 $\color{black}{s\text{ × }t}$ 的矩陣 $\color{black}{C}$ ,其中 $\color{black}{C_{ij} \equiv (A_i * 10^5 + B_j + 1) ^ {-1} \pmod{10^9+7}}$ 且 $\color{black}{0 < C_{ij} < 10^9+7}$。

對於矩陣的第 $\color{black}{i}$ 列,皮皮定義其「皮皮特徵」能用以下方式得出:

$\color{black}{p_0 = 0}$
$\color{black}{p_{j \space (1 \le j \le t)} = (p_{j - 1} \space xor \space (C_{ij} * j)) + j}$

皮皮特徵即為 $\color{black}{p_t}$。

由於皮皮很忙,只好把計算的工作交給你。

輸入說明

第一列有兩整數 $\color{black}{s, t (1 \le s \le 1000, \space 1 \le t \le 100000)}$ 表示序列長度。

第二列為 $\color{black}{A_1 \sim A_s (0 \le A_i < 10000)}$。

第三列為 $\color{black}{B_1 \sim B_t (0 \le B_i < 100000)}$。

輸出說明

依序輸出 $\color{black}{1 \sim s}$ 列的皮皮特徵。

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

(((((0 xor (1 * 1)) + 1) xor (500000004 * 2)) + 2) xor (333333336 * 3)) + 3 = 7
(((((0 xor (943660570 * 1)) + 1) xor (540539193 * 2)) + 2) xor (443036712 * 3)) + 3 = 929591318

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


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