CF 900 D - Unusual Sequences
問題
問題概要
数列について、かつを満たすような数列が何種類存在するか、で割った余りを求めよ。
アイデア
まず、数列の全てのgcdがであるということは、数列の全ての要素はの倍数であるということになる。よってその和もの倍数でないと数列は存在し得ない。
つまり、がで割り切れない時、答えは0であり、割り切れる時、条件はかつと言い換えられる。
では、数列の全要素の和がで全要素のgcdが1であるような数列の個数をで表す。つまり、この問題で求めたいものはである。
また、数列の全要素の和がである(gcdは問わない)ような数列の個数をとすると、とには以下のような関係がある:
上の式からだけをΣの外に出して移項すると、
また、は直接計算することが出来る。個の1が並んでいる状況を想定して、個の間にそれぞれカンマを入れるか否かによって全ての数列を対応付ける事できる。よって、である。以上のことから、
となる。の約数の個数はであるから、後はこれを再帰的にメモ化しながら計算すれば十分間に合う(本当に十分速かった(15ms)(submission))。
メビウスの反転公式による高速化
この式に注目しよう:
の約数を列挙して、の和を考えているが、がの約数全てを動く時、によって列挙されるものもまたの約数全てということになるので、以下の用に書いても差し支えないことに気づく:
上の式にはメビウスの反転公式が適用できる:
これによって、の約数を列挙し、直接を計算できる(solve2で実装)。
実装(C++)
続きを読む2018/1 solved(2)
1/17
水の量と砂糖の量を全探索する。砂糖の量は、bool配列などにその量が作れるかを持っておけば計算量的にOK(submission)。
Warshall-Floyd法によって、最短距離を計算して、入力と一致するかをチェックする。一致すれば、それは入力として妥当なものであり、あとは各頂点対の間に本当に道があるのかを判定する必要があるが、Warshall-Floyd法の更新と同じ要領で、他の頂点を経由してその最短距離を実現できるかを判断材料にすると良い(submission)。
dp[i][j] := 頂点iを色j(黒or白)で塗る時のもう片方の色の重みの最小値
を計算する。最初は、もう片方の重みがkの時、到達可能かを持とうとしたが、間に合わない。でも、できるだけ小さくしとけば今注目している頂点でいくらでも調整が効くので、最小値だけで良いということに気づく(submission)。
1/18
1/19
UF + 並列二分探索。ある距離以上の頂点同士を結ぶグラフを考え、その頂点のみを使って移動可能かどうかは、UFで判定できる。それを一辺に二分探索するために並列二分探索にする(submission)。
1/20
COLOCON -Colopl programming contest 2018- Finalに参加
ABCDの4完。Cに時間かかりすぎ。ConvexHullTrickよく分かってなかった(反省)。
1/21
1/22
setで約数の位置に各値を入れて管理しておくと、次に入るべき値が何になるかは、最後に入れた値の約数ごとに最小値を取っていって(同じ約数を持っている中では小さいものを取ったほうが得なので)、LCMが小さくなるものをとれば良い(submission)。
1/23
CF #451(Div.2) Virtual
ABCDEの5完、Fもあらかたの方針は立ってたけどPythonで突っ込んだのはアホだった(入力サイズがなので)。
1/24
aとbの桁数が多い方とcの桁数は同じor1だけ大きいという関係から、+と=の位置の組み合わせの候補は通りになる。後はそれぞれの場合について、a+b=cが成り立つかをチェックする必要があるが、pythonだとTLEした(参考)(まあだしなあ...)。10をbaseにしたローリングハッシュをつかうことによって、この判定を高速にできるようになる(submission)。
頂点をprince、辺をprincessに対応させたグラフを考えると、連結成分(頂点数)に対して、辺は本までしかはることが出来ないことが分かる(princeとprincessを対応させるので、それはそうで、本はってあるときには対応のさせ方がちゃんとある)。なのでUnionFindをつかったKruskal法を少し工夫して、UnionFind内で、1回だけ同じグループ内で辺を繋ぐことを許す(実装だとnamori
というフラグでUF内に実装してある)ことにしたMSTみたいなことをやる(submission)。
1/25
1/26
とりあえず最低限必要な量を埋めて、後は容量の多い方から貪欲に入れていく(submission)。
要素を取ったら右にしか動かせないことにする(反転した数列に対しても反転すればこれは問題の条件を損ねない)。すると、番目を動かすことにしたら、その後挿入する位置が分割地点にならないと動かした意味が無いのでそこが分割地点になると考えると、番目の要素を含んでいるprefix sumの中から、その要素を引いたものがちょうど半分になるものを見つけるという問題になり、setで管理すれば良い(submission)。
1/27
1/28
1/29
1/30
下の位から払う額を決めていく桁dpをする(submission)。
CF #455(Div.2) Virtual
ABCDEの5完。DもEも厳密には分かってなかったけど、気持ちを実装したら通った。
1/31
筆算の要領で割り続けていき、循環したら打ち切れば良い(今回は十分な回数のloopを取った)(submission)。
番目の要素を取り除いた時にどうなるかを順番に走査しながら最大値を更新していく。この時必要になるのが、左側の値の最大値とその時のレコード数、右側については以上の値で最も近いものとその時のレコード数である。左側については貪欲に更新しておけばよく、右側はindexをsegtreeで管理すると見つけることが出来る(submission)。