Kill/Death [第4回 ドワンゴからの挑戦状 予選 C]

https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_c

前提知識

• 動的計画法
• 分割数

解法

https://dwacon2018-prelims.contest.atcoder.jp/submissions/1971517

ちなみに、以下の解法よりもより良い解法がある（後ろにも全て置くという発想すごすぎ）
以下の解法は分割数を利用した解法になる。

誰が誰を倒したかというのは任意に変えられるので、
普通では味方のデス数の総和と敵のキル数の総和が一致していれば何でもいい。
しかし、今回はキル数が同じ場合はデス数の昇順となっているというのが問題である。
つまり、以下の2条件をみたす数列を作る組合せを考えることになる。

• デス数の総和は相手のキル数の総和と等しい
• キル数が同じ区間ではデス数は広義単調増加する

キル数が同じプレイヤーを1つのグループにまとめる。
「dp[g][sm] := g番目のグループまででデス数がsmである組み合わせ数」
これを求める。
dp[g + 1][sm + i] += dp[g][sm] * (g+1番目のグループでデス数の総和がiとなる組み合わせ数)
で更新できるため、「(g+1番目のグループでデス数の総和がiとなる組み合わせ数)」を考えてみよう。
これは丁度分割数の応用で計算ができる。
このサイトを参考にすると、
「Q(n,r) := 整数nを順序を区別せずに「r個の自然数」の和に分ける場合の数」
を使えばよさそう。漸化式は「Q(n,1) = 1 (n≧1), Q(n,n) = 1 (n≧1), Q(n,r) = Q(n-1,r-1) + Q(n-r,r) (n≧r≧2)」
このままでは、自然数なのでデス数が0のプレイヤーを計算できないので、累積和を使って以下のようにする
「R(n,r) := 整数nを順序を区別せずに「r個以下の自然数」の和に分ける場合の数」
「R(n,r) = R(n,r-1) + Q(n, r)」の漸化式で累積和のように計算しよう。
この関数Rが丁度、「(g+1番目のグループでデス数の総和がiとなる組み合わせ数)」となる。
　
これをA側、B側でそれぞれ行い、場合の数を掛け合わせると答えになる。

PartitionNumber<mint> pn(1010);
mint solve(vector<int> &kill, vector<int>& death) {
    deque<pair<int, int>> cnt;
    cnt.push_back({ kill[0], 1 });
    rep(i, 1, kill.size()) {
        if (cnt.back().first == kill[i]) cnt.back().second++;
        else cnt.push_back({ kill[i], 1 });
    }

    int sm = 0;
    fore(i, death) sm += i;
    int n = cnt.size();

    vector<vector<mint>> dp(n + 1, vector<mint>(sm + 1, 0));
    dp[0][0] = 1;
    rep(g, 0, n) rep(s, 0, sm + 1) rep(i, 0, sm - s + 1) dp[g + 1][s + i] += dp[g][s] * pn.R(i, cnt[g].second);

    return dp[n][sm];
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int N, M;
    cin >> N >> M;

    vector<int> A(N), B(M);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, M) cin >> B[i];

    mint a = solve(A, B);
    mint b = solve(B, A);
    mint ans = a * b;
    cout << ans << endl;
}