読者です 読者をやめる 読者になる 読者になる

Codeforces Round #174 Div2

A. Cows and Primitive Roots

http://www.codeforces.com/problemset/problem/284/A

素数pについて x - 1, x2 - 1, ..., xp-2 - 1 (mod p) != 0 かつ xp-1 (mod p) == 0 が成り立つx (1 <= x < p) を、pのPrimitive Rootといいます。日本語では「原始根」といいます。

素数pを与えるので、原始根の個数を表示して下さい。


原始根についての解説はこちらが詳しいです。が、高度すぎて私にはさっぱり理解出来ません^^;

既約剰余類群と原始根 - epii's physics notes

実は、xがpの原始根であるときは gcd(p-1, x) が成り立つという性質があるということなので、オイラーのΦ関数を使えば一発で解けるようなのですが、そんなことはGoogle先生に聞かないと分からない(というのが普通だと思うのですが…)ので、問題文に書いてあることを愚直に実装しましょう。A問題ですし。

しかしながら、pの値が取る範囲は 2 <= p < 2000 となっているので、 xp-1 なんて計算できません。ここで mod p に着目する必要があります。

蟻本にも書いてありますが(第2版なら114ページ)、 a%m == c%m かつ b%m == d%m のときは以下の3つの等式が成り立ちます

  • (a + b)%m == (c + d)%m
  • (a - b)%m == (c - d)%m
  • (a * b)%m == (c * d)%m

ここから、大きな累乗の余りを求めるのに便利な方法が導き出せます。

(k*k)%m を求める場合について考えてみましょう。

上の式より ( (k%m)*(k%m) )%m ですね。

次に (k*k*k)%m について考えてみましょう。

こちらは (k*k)%m の結果を流用することにすると ( ((k*k)%m)*(k%m) )%m となりますね。

xk が桁あふれを起こす場合でも xk%mは m < sqrt(INT_MAX) ならば桁あふれを起こさずに計算できることが分かるかと思います。

余りを取りながら累乗を計算するときには「繰り返し二乗法」によって高速化することもできます(詳細は蟻本を参照して下さい)。ICPC用のライブラリに入れるのを忘れていたので、今日にでもライブラリ化しようと思います。ただし、今回は、たかだか2000回のループをするだけで良いので繰り返し二乗法は必要ないような気もします。

僕はクズなので、Pythonの標準ライブラリに含まれているpow()関数を使いました。pythonのpow()関数には第3引数があって、x**y%zを高速に計算してくれます。

しかしながら、そこまで知っていつつもxrange()の引数を勘違いしていて、全く点数を稼げませんでした。xrange(a,b) は [a, a+b) ではなくて [a, b) です。みなさん勘違いしないようにしましょう!!!

B. Cows and Poker Game

http://www.codeforces.com/problemset/problem/284/B


readforcesで意味がよく理解できていなかったのですが、なぜか通せました。 以下のブログの方が翻訳してくれているので、そちらを参照して下さい。

Codeforces #174, Division 2, B : Cows and Poker Game - torus711のアレ

C. Cows and Sequence

http://www.codeforces.com/contest/284/problem/C

数列に対する操作がn個与えられます。その数列の初期状態は1つの0です(C言語風に書けば { 0 } )。

数列に対する操作は以下の3種のどれかです。

  1. 数列の先頭のa個の要素それぞれに対してxを足す
  2. 数列の後ろにkという要素を追加する(すなわち、数列の要素数が1増える)
  3. 数列の最後の要素を消す(すなわち、数列の要素数が1減る)

それぞれの操作が終了したあとに、数列の平均値を小数点以下6桁まで表示して下さい。 なお、数列の要素が全て消されるような不正な操作は絶対に行われません。

制限: 1 <= n <= 2*105, -103 <= x, k <= 103


明らかにBIT (Binary Index Tree) に関する問題ですが、1番の操作が難しそうです。

まだ理解できていないものを解説するのもアレなのですが、区間に対して値を加える操作はBITを2つ使うことによって効率的に行えます。

以下のような操作を実装したBITを2つ作り、bit0、bit1とします。

  • bit::add(i,x) → 0-indexedでのi番目の要素にxを足す
  • bit::sum(i) → [0, i) の合計を返す

次に、区間に対する操作を実装した関数を実装します。[l, r)にxを足す関数をadd(l, r, x)、[l, r)の和を計算する関数をsum(l, r)とします。

add(l, r, x)

  • bit0.add(l, -x * l);
  • bit1.add(l, x);
  • bit0.add(r, x * r);
  • bit1.add(r, -x);

sum(l, r)

  • bit0.sum(r) + r*bit1.sum(r) - bit0.sum(l) - l*bit1.sum(l);

各操作を行うためには、このほかにも要素数を表す変数lenが必要です。

数列の初期値は{0}なので、最初は len=1 です

  1. の操作は add(0, a, x) です
  2. の操作は add(len, len+1, k); の後 len++ します
  3. の操作は len-- してから int s = sum(len, len+1); で最後の要素の値を求め、add(len, len+1, -s); としてその値を消して0にします

ここで、注意が2点あります。

まず、和を求める関数のsumとbit::sumの返り値はintではいけません。桁あふれします。

次に、BITの節点の値を格納するコンテナ(配列だったりvectorだったり)の型もintではいけません。BITの原理を良く思い出して下さい。確かに、数列の各要素の値は2*105*103の範囲に収まるので、intでも良さそうですが、BITの節点は子の合計値を格納するので、intの範囲に収まりません。