Darsein https://blog.hatena.ne.jp/Darsein/ Darseinのプロコン日記 https://darsein.hatenadiary.org/ 個人的に好きなタイプの問題だったので久しぶりに解説を書きます。 問題 アルファベット小文字('a'-'z')からなる任意の文字列を考える。 長さN以下、含まれる文字の種類数K以下の回文の個数を求めなさい。 ただし、数が大きくなりうるので1234567891の剰余を返しなさい。制約: 1 解法 まずは高速なアルゴリズムを一旦無視して、答えを数式にしてみる。 を、「長さがちょうどiで文字種類数がちょうどjの回文の個数」とする。 すると答えは、となるので、これを求めたい。ここで、回文は前半が決まってしまえば後半は一意に定まるという特徴を考えると、 n/2文字の任意の文字列を作れば、その対称をとること… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdarsein.hatenadiary.org%2Fentry%2F20140708" title="SRM428 Div.1 500 The Long Palindrome - Darseinのプロコン日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/D/Darsein/20140708/20140708125922.png Hatena Blog https://hatena.blog 2014-07-08 00:00:00 rich https://darsein.hatenadiary.org/entry/20140708 1.0 100%