この問題は、入力の種類数を減らす工夫をすることで、解を埋め込むことが可能です。

この問題の解は文字の順番を変えたり、ある文字を別の文字と入れ替えたりしても変化しません。例えば、サンプル2では \(S\) は zzyyx ですが、 \(S\) を xyzzy や aabbc や level に置き換えたとしても答えは変わりません。

そのため、各文字ごとに \(S\) 中の出現回数を数え、文字を無視して出現回数の分布だけ見ることで、複数の \(S\) をひとつに纏めることができます。例えば zzyyx であれば、 x が \(1\) 個、 y が \(2\) 個、 z が \(2\) 個であるため、出現回数を降順に並べ \((2, 2, 1)\) と表すことができます。

ある \(N\) に対して考える必要がある \(S\) の種類数は \(N\) の分割数 \(p(N)\) と等しくなります。 例えば、 \(N=5\) の場合は \(p(5) = 7\) 、 \(N=10\) の場合は \(p(10) = 42\) です。 なお、分割数の説明はWikipediaに譲ることとします。

このように考えると、入力の種類数は各 \(N = 1, 2, \ldots, 10\) ごとに \(K\) が \(N\) 種類で \(S\) が \(p(N)\) 種類、あわせると \(\sum_{N = 1}^{10} N p(N) = 1106\) 個となり、これは解を埋め込んでもソースコード長制限に引っかからない程度の大きさです。

整数の分割の列挙

解の全列挙には整数の分割を列挙する必要があるため、以下ではその方法を紹介します。

非負整数 \(n\) を \(1\) 以上 \(m\) 以下の整数に分割する方法は、以下のとおり再帰的に実装することができます。

• \(n = 0\) のとき: 空列の \(1\) 通りです。
• \(n > 0\) のとき: 各 \(i = 1, 2, \ldots, \min\{n, m\}\) について、分割の先頭は \(i\) となり、のこりは \(n - i\) を \(1\) 以上 \(i\) 以下の整数に分割する方法と同じになります。

これをジェネレータを使って実装すると、以下のようになります。

def partition(n, m):
    if n == 0:
        yield ()
        return
    for i in reversed(range(1, min(n, m) + 1)):
        for rest in partition(n - i, i):
            yield (i, ) + rest

コードの生成

dict に入力と解の組み合わせを入れていくことで、非常に簡単に埋め込むことができます。

以下はコードを生成するコードの一例です。

from more_itertools import distinct_permutations

def partition(n, m):
    if n == 0:
        yield ()
        return
    for i in reversed(range(1, min(n, m) + 1)):
        for rest in partition(n - i, i):
            yield (i, ) + rest

def solve(K, S):
    N = len(S)
    ans = 0
    for p in distinct_permutations(S):
        if not any(p[i:i + K] == tuple(reversed(p[i:i + K])) for i in range(N - K + 1)):
            ans += 1
    return ans

# dict に入力と解のペアを入れる
embedded = {}
for N in range(1, 10 + 1):
    for K in range(1, N + 1):
        for S_key in partition(N, N):
            # 入力を生成
            S = []
            for i in range(len(S_key)):
                S += [i] * S_key[i]
            embedded[(K, S_key)] = solve(K, S)

# コードを生成
print(f"""
from collections import defaultdict

N, K = map(int, input().split())
S = input()

count = defaultdict(int)
for c in S:
    count[c] += 1

S_key = tuple(reversed(sorted(count.values())))

embedded = {embedded}

print(embedded[(K, S_key)])
""")

なお、コードの生成には数分程度を要するため実行の際はご注意ください。

このコードで生成された提出: Python (27 ms)