AOJ3336 Fish Tank

備忘録。想定解をそのまま追っかけただけの記事なので新規性は無いです。

問題概要

https://onlinejudge.u-aizu.ac.jp/problems/3336

長さの広義単調減少列が与えられる。以下の操作を何回か行うことを考える。

• 添字を一つ選んで、を増やす。

各操作の前後では広義単調減少でなければならない。全てのをにする操作の仕方の通り数をで割ったあまりを求めよ。

制約

• 
• 
• は広義単調減少

解法

https://drive.google.com/drive/folders/1KoV507hNY39alt9nXGOu0OjRS2tEyH2b

• 想定解はM.pdfに書かれている。

ヤング図形で考える。操作はいずれかの行を選び、右端に正方形を一個追加することと同じ。操作後もヤング図形で無いといけない。

・・・こっち側もヤング図形だな。

条件を満たしながら目的を達成する操作を手順を一つ取る。置いた正方形の順番をヤング図形に書き込む。順番の降順に数を書くと、標準盤になっていることがわかる。

反対に標準盤を一つ取って、書かれた数の降順に操作を行う(正方形を置く)と条件を満たしながら目的を達成することができる。

よって標準盤の数を数えれば良いことがわかる。標準盤の数についてはフック長の公式というものがあって、この公式を素直に適用すると で数え上げることができる。

using mint = atcoder::modint998244353;

int main() {
    SetFastIO();

    int n, m; std::cin >> n >> m;
    std::vector<int> a(n);
    int sum{};
    for (int i{n - 1} ; i >= 0 ; i--) {
        std::cin >> a[i];
        a[i] = m - a[i];
        sum += a[i];
    }

    mint num{1};
    for (int i{1} ; i <= sum ; i++) num *= mint::raw(i);
    mint den{1};
    for (int i{} ; i < n ; i++) {
        int dn{n - 1};
        for (int j{} ; j < a[i] ; j++) {
            while (j >=  a[dn]) dn--;
            // std::cerr << i << ' ' << j << ' ' << dn << ' ' << a[i] - j + dn - i << std::endl;
            den *= mint::raw(a[i] - j + dn - i);
        }
    }

    mint ans{num / den};
    std::cout << ans.val() << '\n';
}

感想

知らないと詰んでしまうタイプのテクニック、どっかにまとめておきたい。