yukicoder181 A↑↑N mod M
$M$をいかしたい。$A^{x} ≡ A^{x \, mod \, φ(m)} mod \, m$であるから、実際に再帰をしていく際に$mod$が小さくなっていく。($φ(m)<m$なので)
これがわかれば後は再帰をしていくだけ。
また$A^x$の周期は完全ではなく準周期なのでそこに注意する。
計算量:$O(MlogN)$(自信なし)
Submission
yukicoder182 新規性の虜
値が大きいのでMapに値をのせて、登場回数を見れば良い。
計算量:$O(NlogN)$
Submission
yukicoder183 たのしい排他的論理和(EASY)
$a$が小さいので、$dp[x]:=$xorの値が$x$にできるか否かとしてdpできる。
計算量:$O(N*SZ)$ ($SZ=2^{15}$)
Submission
yukicoder184 たのしい排他的論理和(HARD)
解説の通り。$N$本$32$要素のベクトルがあるので生成できるベクトルの数は?と読み替えることができる。
行列とみれば$2^{Rank}$が答え。
計算量:$O(NlogN)$
Submission
yukicoder185 和風
Mapに答えをのせて一致するかを確認する。
計算量:$O(NlogN)$
Submission
yukicoder186 中華風(Easy)
中国剰余定理で解けるがほぼ覚えていなかったので勉強し直した。
計算量:$O(NlogN)$
Submission
yukicoder187 中華風(Hard)
さっきの問題を中国剰余定理で解いていれば貼るだけっぽいが、オーバーフローしてしまう。
Garnerのアルゴリズムを用いればできる。
非常に参考になったdrkenさんの記事！↓
中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ
計算量:$O(N^2logN)$
Submission
yukicoder188 HAPPY DAY
全部調べる。
計算量:$O(1)$
Submission
yukicoder189 SUPER HAPPY DAY
典型桁DP。$dp(i,s):=i$番目の桁を見たときに桁の総和が$s$になる組み合わせ数として解ける。
再帰の計算量は抑えられるがあまり影響のないタイプ。
計算量:$O((|M|+|D|)*(MAX))$ ($MAX:$桁の和の最大値)
Submission
yukicoder190 Dry Wet Moist
これをしゃくとり法と呼ぶかわからないがしゃくとり法っぽく貪欲にやると線形でできる。
計算量:$O(NlogN)$
Submission