inamori https://blog.hatena.ne.jp/inamori/ inamori’s diary https://inamori.hateblo.jp/ https://atcoder.jp/contests/abc456/tasks/abc456_g久しぶりに解説を見てみたら、母関数を使う方法が書いてありました。 Sをxで分割して、それぞれの領域の長さをとして、日のうち連続する休日が日までの場合の数をとすると、求める場合の数は、となります。なので、このを求めればよいです。 休日をo、勤務日をxで表すと、oは個まで続いていいので、x、xo、…、xo…o（oが個）を組み合わせて結合すればいいです。ただしこれだと必ずxから始まるのでの長さをまでの長さで分割することにします。例えば長さ3を1以下で分割するなら、 1 1 1 1 => x x x x … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finamori.hateblo.jp%2Fentry%2F2026%2F05%2F22%2F125024" title="AtCoder Beginner Contest 456 G - inamori’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2026-05-22 12:50:24 rich https://inamori.hateblo.jp/entry/2026/05/22/125024 1.0 100%