人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選:C - チップ・ストーリー ~白銀編~

問題

beta.atcoder.jp

解法

P_i の最大値を maxP,Q_i の最大値を maxQ とおく.この時,maxP を 1 ~ N で動かすとき,maxQ は [ N / maxP ] になる.P の通り数は maxP^10 - (maxP - 1)^10 になる(なぜならば,最終的な通り数を求める段階で重複が発生してしまうから).maxP に対応する Q の通り数は maxQ^10 になる(なぜならば,前述の P の通り数で重複分は対応できているから).これらを掛けたものを足し合わせたものが答えになる.実装面では,mod した数同士の引き算で負になってしまうかもしれないので + mod してから mod を取ることを気を付ければいい.累乗した数を前計算しておき O(N).

解答

beta.atcoder.jp

実装面でかなり手こずってしまった.計算量をガン無視していて 1 TLE した.

f:id:babcs2035:20181123224413p:plain