新たに作られる整数のうち 33...33 で割り切れる数が奇数個あれば ahri が勝ち、偶数個あれば teemo が勝ちます。

愚直に考えると KK 個の整数を並び替えて作られる新たな整数は NCK×K!_{N}C_{K} \times K! 通りありそうですが、全ての組み合わせを実際に並び替えて試すのは厳しそうです。 そこで、実際に並び替えずに処理する方法を考えます。 各桁の合計を調べる 33 の倍数判定法は有名ですが、同じようにして 33..3333..33 の倍数も判定してみます。

例えば、サンプル2の 3333 で割り切れる数 376464376464 について 376464=37×(9999+1)+64×(99+1)+64376464 = 37 \times (9999+1) + 64 \times (99+1) + 64 より 37+64+6437+64+643333 の倍数なら 3764643764643333 で割り切れると分かります。 一般的には「任意の整数 AAXX 桁の 33...3333...33 で割り切れるかどうか」は「任意の整数 AA を下位から XX 桁ずつ区切った数の総和が 33...3333...33 の倍数かどうか」で判定できると言えます。

入力された NN 個の整数から KK 個の整数を選んだとき、その KK 個の整数合計が 33...3333...33 の倍数ならば、その KK 個の整数を並び替えて作られる K!K! 通りの整数すべて 33...3333...33 の倍数と言えます。 したがって NN 個の整数から KK 個の整数を選ぶ組み合わせ NCK_{N}C_{K} 通りについて 33...3333...33 の倍数かどうか調べるだけで良く、計算量は O(2N)O(2^N) で済みます。 なお、実装するときは set などを使って KK 個ずつの整数集合をダブルカウントして計算しないように管理し、選択した KK 個の中に a個, b個, ... の同じ整数が含まれていたとき K!/(a!×b!×...)K!/(a! \times b! \times ...) 通りの順列になることに注意します。