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

hamayanhamayan's blog

長方形の敷き詰め [yukicoder 1186]

https://yukicoder.me/problems/no/1186

解説

https://yukicoder.me/submissions/537703

パッと見て、難しい問題に見えるが、ピースの横幅と、長方形の縦幅が一致している所に弱点がある。

M < Nのとき

このとき、ピースを横置きしていくしかない。
これは1通りしかないので、それを答える。

そうじゃない場合はどうだろうか

この場合は縦置きも可能。
さて、仮に1つ横置きすると、下の部分には縦置きできないので、ずっと横置きすることになる。
なので、横置き部分、縦置き部分のグループが交互に出てくる感じになるので、
この組み合わせを数えていけばいい。

横置きできるグループの個数の上限はM/N個なので、横置きの個数を全探索して、二項定理で組み合わせを計算しよう。

int N, M;
Comb<mint, 2010101> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;

    if (M < N || N == 1) {
        cout << 1 << endl;
        return;
    }

    mint ans = 0;
    rep(yoko, 0, M / N + 1) {
        int rest = M - yoko * N;
        ans += com.aCb(rest + yoko, yoko);
    }
    cout << ans << endl;
}