c683: 機遇之池
標籤 : 除法優化
通過比率 : 43% (3 人 / 7 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-08-25 22:49

內容

舉凡網路、手機遊戲,除了組隊刷怪之外,最刺激的莫過於那些無法掌控的元素吧!

你永遠不知道寶箱之內是否藏著陷阱,也從來猜不透下次抽出的卡牌。

現在 Black & Orange 遊戲公司推出一個稱作「機遇之池」的活動,將一樣道具投入池中,便能改變它的數值,奇妙的是,這個過程也會被上個使用池子的玩家影響。

經過長時間的觀察,似乎有人已經發現「機遇之池」的演算方法,但為求謹慎,你希望能迅速比對網路上找到的資料。

void f(uint32_t &x, uint32_t &c, uint32_t d) {
	for (int k = 0; k < 16; ++k) {
		c += ((x << k) | (x >> (32 - k))) / d;
		c += ((x >> k) | (x << (32 - k))) / d;
		x += c * 2654435761lu;
	}
}

遊戲裡使用無號32位元整數儲存數值。

「機遇之池」隱含了長度 $\color{black}{N}$ 的序列 $\color{black}{S}$,而道具一開始的數值為 $\color{black}{x}$ ,和初始為零的隱藏變數 $\color{black}{c}$。

假設上一個玩家的轉化成果為 $\color{black}{last}$ (沒有上一個就視為0), 對於每個$\color{black}{S_i}$,伺服器首先會將 $\color{black}{x}$ 變為 $\color{black}{x\space xor\space last}$,再執行$\color{black}{f(x, c, S_i)}$,$\color{black}{N}$輪運算後的$\color{black}{x}$即為轉化數值。

輸入說明

第一行是兩個非負整數 $\color{black}{N, M \le 10000}$,分別為序列長度和參與的玩家數目。

第二行有$\color{black}{N}$ 個整數 $\color{black}{1 \le S_i < 2 ^ {32}}$,為序列內容。

第三行有$\color{black}{M}$ 個整數 $\color{black}{1 \le x_i < 2 ^ {32}}$,$\color{black}{x_i}$代表第$\color{black}{i}$位玩家投下的道具數值。

輸出說明

道具的轉化結果。

範例輸入
3 4
2 2 2
20 20 20 20
範例輸出
3997325084
2705072328
1928591162
836263515
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (16%): 1.0s , <1K
公開 測資點#1 (16%): 2.0s , <1M
公開 測資點#2 (17%): 2.0s , <1M
公開 測資點#3 (17%): 2.0s , <1M
公開 測資點#4 (17%): 2.0s , <1M
公開 測資點#5 (17%): 10.0s , <1M
提示 :
標籤:
除法優化
出處:
[編輯:
icube (迭)
]


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