ARC116 C - Multiple Sequences
これが水diffって嘘だよな......
エスパーで通してしまった。解説見てなるほどな〜になった
https://atcoder.jp/contests/arc116/tasks/arc116_c
問題概要
以下の条件を満たす長さ の整数列
の個数を求めよ。
は
の倍数
解説
問題を見ると、 ...
番目の要素が
である
の個数 という自明な DP が思い浮かぶが、これは解けない（コンテスト中はずっとこれの高速化を考えてしまった）。
末尾の要素を固定するといい感じに数えられそうな予感がする。末尾の要素を固定し、それぞれに対して の個数を高速に求めることを考える。
の要素数を
だと考え、
としても問題ない。最初の要素も固定されるので嬉しい。
のときを考える。
それぞれに
の素因数を配る感じになる。
このとき、素因数ごとに独立に考えて良い。つまり、 と素因数分解すると、
は独立に考えてよい。
個の
を
個の箱に配ればよくて、これは
通りである。それぞれの素因数に対するこの値の総積が、末尾が
のときの答え。あとは
から
まで足せばよい。
素因数の個数の和は調和級数を考えると で抑えられるので、間に合う。
反省
DP から抜け出すのが遅かった。末尾固定は考えられたが、 を追加し最初の項も固定するとより考えやすくなったので、吸収したい。組み合わせの基本的なところ（写像 12 相など）がパッとできないので訓練したい......。
