http://yukicoder.me/contests/159
解説です。
yukicoder No.490 yukiソート
http://yukicoder.me/submissions/156505
書かれているアルゴリズムを素直に実装するだけ。
yukicoder No.491 10^9+1と回文
http://yukicoder.me/submissions/157172
10^9+1の倍数かつ回文である数は、以下の性質を満たす。
- A + B + A : Aは回文の数,Bは0が連なったもの
- len(A) + len(B) = 9
2番目の性質より、len(B)=0の時に18桁となって最大。
Bは0が9-len(A)個だけ連なったものなので、Aによって一意に決定。
Aを全探索すればよい。
Aはそのまま全探索すると10^9となってしまうが、回文となるため半分全列挙が使える。よって10^5くらいとなるので間に合う。
yukicoder No.492 IOI数列
https://yukicoder.me/submissions/157179
別々に問題を解く。
関数solA : mod10^9+7
行列累乗で解く。漸化式から行列を作ると以下のようになる
| a[i+1] | | 100 1 | | a[i] | | 1 | = | 0 1 | * | 1 |
この行列を事前に行列累乗で計算しておくことにより、素早く漸化式を解くテクニック
関数solB : mod1010…
modのbaseがlong longに乗らないので、別方針で考える。
規則性がある
1 -> 101 -> … -> 101010101010101010101 -> 0 -> 1 -> …
周期が11回なので、N %= 11としてしまって問題無い。あとはi番目の文字数はi * 2 - 1個なので上手いこと文字列を作って返す。(N == 0の時は"0")
yukicoder No.493 とても長い数列と文字列(Long Long Sequence and a String）
https://yukicoder.me/submissions/157186
漸化式で区間クエリだとよくある問題。
Kは62くらいが上限なので、それ以上の数であっても62くらいにしておく。
区間でよくあるテクで[L,R]を考える時に[0,L]と[0,R]を計算してなんとかするやつがある。
なので、[0,x]の区間について和と積を考える。
事前計算(pre関数)をしておく。
sz[i] = f(i)の要素数
sm[i] = f(i)を文字列化したものの総和
mu[i] = f(i)を文字列化したものの総積
これは漸化式から簡単に求まる。
あとはcalcSumとcalcMulを作るだけだが、和と積は計算部分だけ違うので、calcSumだけ説明する。
calcSum(int k, ll x) := f(k)のx番目までの総和
- x==0ならreturn 0(0番目までってことは何もない)
- x <= sz[K - 1]なら、f(k-1) + k^2 + f(k - 1)の前半部分だけの総和なので、return calcSum(k - 1, x)とする
- x <= sz[k] - sz[k-1]なら、f(k-1) + k^2 + f(k - 1)の前半部分全部とk^2の一部（または全部）なので、return sm[k - 1] + (k^2の該当範囲の和)
- それ以外なら、f(k-1) + k^2 + f(k - 1)の前半とk^2とを全部 + 後半部分の一部なので、return sm[k-1] + (k^2全部の和) + calcSum(k - 1, x - (sz[k] - sz[k-1]))
