はまやんはまやんはまやん

hamayanhamayan's blog

Multiplicity [Codeforces Round #523 (Div. 2) C]

http://codeforces.com/contest/1061/problem/C

N個の配列Aがあり、ここから(連続してなくてもいい)部分列を取ったものを配列Bとする。
配列Bは全てのiについて、B[i]がiで割り切れるときに良い配列とされる。
全ての部分列について良い配列であるのは何通りあるか。

前提知識

考察過程

1. DPっぽさがある
2. さっくり考えると「dp[i][j] := i番目までの部分列で長さがjの良い配列の組み合わせ」
3. A[i]での遷移を考えると、遷移先のjはA[i]の約数しか無い
4. 遷移が限られていて、他の要素はそのまま
5. インラインDP

解説

http://codeforces.com/contest/1061/submission/46096345

DPをする。
dp[i][j] := i番目までの部分列で長さがjの良い配列の組み合わせ
これを更新していくが、遷移先はA[i]の約数分しかない。
例えばA[i]=6であれば、これは1,2,3,6番目になるしかないので、dp[i+1][1], dp[i+1][2], dp[i+1][3], dp[i+1][6]しか更新できるところがない。
他の部分はdp[i+1][j] += dp[i][j]という感じになる。
 
このように一部が変更されるだけで、他は変わらないという場合はインラインDPが使える。
予め、約数を持った配列を作っておこう(配列vd)。
これはエラトステネスの篩のような感じにやればO(10^6log10^6)で作れる。
dp[i+1][j]はdp[i][j-1]を使って更新するので、約数を大きい順に使って更新していく必要がある。
配列vdは降順ソートで持っておこう。

const int MA = 1010101;
int N, A[101010];
vector<int> vd[1010101];
mint dp[1010101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    rep(d, 1, MA) for (int x = d; x < MA; x += d) vd[x].push_back(d);
    rep(i, 0, MA) reverse(all(vd[i]));

    dp[0] = 1;
    rep(i, 0, N) fore(d, vd[A[i]]) dp[d] += dp[d - 1];

    mint ans = 0;
    rep(i, 1, 1010101) ans += dp[i];
    cout << ans << endl;
}