kazuma8128’s blog

競プロの面白い問題を解きます

畳み込み

CodeChef SPC19F1 Lockied Away

問題文 https://www.codechef.com/SPCM2019/problems/SPC19F1 問題概要 N が与えられるので、積がN以上となるような非負整数のマルチセットのうち, 和の最小値を求めよ. Nは桁数が 2*10^6 以下の非負整数. 解法 4 = 2 * 2 , 5 当然1もいらなくて (ただしN=1…

CodeChef IMGOD Apun Hi Bhagwan Hai !

問題文 https://www.codechef.com/problems/IMGOD 問題概要 整数N (1 分割する対象が区別できるものでの N の分割数 S(N, i) mod 163577857 (1 解法 これは第二種スターリング数というものらしい.S(n, k) = (1 / k!) * Σ(-1)^(k - m) * kCm * m^n = Σ ( (-1)…

約数集合でのゼータ変換・メビウス変換的なやつと畳み込み

昨日の CodeChef の July Lunchtime 2018 に参加したときに思いついたのでメモ.※何も見ずに書いてるからもしかしたら間違いだらけかもしれないので注意です. ゼータ変換 競プロで使うゼータ変換(?)は, 各集合について, その上位または下位集合の和を求めるや…

巨大modでの掛け算の高速化 (Codeforces Round #259 D Little Pony and Elements of Harmony)

問題 http://codeforces.com/contest/453/problem/D 解法 大体の方針はアダマール変換を使った XOR の畳み込みでできます. あとは mod を p * 2^m (ただ, 今回は mod が 10^9 よりだいぶ大きいので long long でオーバーフローしてしまうため普通に掛け算で…

色々な畳み込み

最近覚えたのでメモ. 理論とか仕組みとかの説明はしません. 高速フーリエ変換(FFT) 添え字和での畳み込み Σ(i + j = k) a_i * b_j = c_k この形で長さ n の列 a, b から長さ 2n の列 c を求めます. ただし n は2の冪乗とします.列 a, b を離散フーリエ変換し…