新たに作られる整数のうち 33...33 で割り切れる数が奇数個あれば ahri が勝ち、偶数個あれば teemo が勝ちます。
愚直に考えると 個の整数を並び替えて作られる新たな整数は 通りありそうですが、全ての組み合わせを実際に並び替えて試すのは厳しそうです。 そこで、実際に並び替えずに処理する方法を考えます。 各桁の合計を調べる の倍数判定法は有名ですが、同じようにして の倍数も判定してみます。
例えば、サンプル2の で割り切れる数 について より が の倍数なら が で割り切れると分かります。 一般的には「任意の整数 が 桁の で割り切れるかどうか」は「任意の整数 を下位から 桁ずつ区切った数の総和が の倍数かどうか」で判定できると言えます。
入力された 個の整数から 個の整数を選んだとき、その 個の整数合計が の倍数ならば、その 個の整数を並び替えて作られる 通りの整数すべて の倍数と言えます。 したがって 個の整数から 個の整数を選ぶ組み合わせ 通りについて の倍数かどうか調べるだけで良く、計算量は で済みます。 なお、実装するときは set などを使って 個ずつの整数集合をダブルカウントして計算しないように管理し、選択した 個の中に a個, b個, ... の同じ整数が含まれていたとき 通りの順列になることに注意します。