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; }