geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC228 参加記録

ABC 出次数1の有向グラフ フェルマーの小定理

コンテスト中AC:A~D

E問題も解いたので記載しておきます。

 

 

B - Takahashi's Secret

i→A_iに有向辺がある有向グラフとみなすと、これは、

・閉路がただ一つ存在する

・全ての頂点から有向辺を辿ると閉路に行き着く

というグラフとなります(こちらに私的見解で証明してみた別問題の解説記事があります)

 

よって、既に秘密を知っている人にぶつかるまでXから辺を辿ればよく、その時に訪問した頂点数(人数)が答えです。

提出コード

 

C - Final Day

iについて、最も順位が小さくなる場合のみを考慮すればよく、それはiが300点を採り、他が0点の時です。そのように考えると、他の人の点数は変わりません。

 

知りたいのは、A_i+300となったときに、自分より大きい人が何人いるかです。

他の人の点数は変化しないので、予めAを昇順にソートしておき、A_i+300より大きい人が何人いるかを二分探索で求めることができます。

 

AはA_iを含むので大丈夫なのか、心配になりますが、A_iよりA_i+300の方が必ず大きくなるので問題ありません。

計算量はソートと各iについての二分探索でO(NlogN)です。

提出コード

 

D - Linear Probing

クエリ1に＋1ずつしていく愚直解だと、

1 1

1 1

...

1 1

という風にクエリが与えられた場合、O(Q^2)となり間に合いません。

 

円環であることを一旦無視すると、A_iが-1であるもののうち、x_i以上で、かつA_k=-1であるkを見つける操作となります。

 

そこで、C++ならsetで、現在-1であるインデックスを記録しておきます。

すると、二分探索(lower_bound)でkを探すことができ、値の削除もlog時間で可能です。

 

円環であることに立ち返ると、最初の探索で値が見つからなかったとき、再度1から探索をやり直せばよいです。

なお、Q\lt Nであることから、2回目の探索で挿入位置が見つからないということはありません。

 

計算量は最初にsetにN個のインデックスを挿入する操作がボトルネックとなると思うので、O(NlogN)となり間に合います。

提出コード

 

E - Integer Sequence Fair

コンテスト中は、過去のARCのこの問題の類題であるということに囚われて、周期を見つけたいが、オイラーのトーシェント関数を求めたりやmodをとったりするやり方が、998244353は大き過ぎて適用できないからどうしよう、となってしまいました。オイラーの定理の例外ケースであるフェルマーの小定理に気づけませんでした。

 

長さがNで要素が1〜Kまでの整数列は全部で、K^Nが存在し、それぞれに1〜Mまでの整数を割り当てるので、M^{K^N}通り存在します。

 

998244353は素数なので、フェルマーの小定理より、

M^{998244353-1}\equiv 1\ mod\ 998244353

が成り立ちます。

 

よって、K^Nを998244353-1の倍数とその余りに分ければ、

倍数部分はすべて1になるので、結局その余りのべき乗のみを考慮すればよくなります。

 

コンテスト後にここまで気づいて、以下のように実装してみました。

p = 998244353とします。

・r = K^N\mod\ (p-1)とする

・ans = M^r\ mod\ pとする

このように素直に実装すると、WAが4つだけ出てしまいました。この時点で公式解説を見たのですが、解決できませんでした。

 

他の方の実装を見るなどして調査した結果、原因が判明しました。

AtCoderライブラリや一般的な繰り返し二乗法では、x^0 = 1として定義されます。

ここで、K = 998244352、N = 3、M = 998244353としてansを計算してみます。

r = {998244352}^3\ mod\ 998244352 = 0

ans = 998244353^0\ mod\ 998244353 = 1\ mod\ 998244353 = 1

 

rというのはあくまで、余りを計算したために生じた値であって、本来なら

998244353^{998244352^3}\ mod\ 998244353

を計算しているので、答えは0になるはずです。

 

この事態を避けるため、Mが998244353の倍数は例外として外す必要があります。

提出コード