コンテスト中にバグらせていた自分の解放がやっと通ったのでメモ書き。
以下の３パターンのうちの満たすものを合計する
１：Nと上からn桁は一致するNより小さいもの
２：Nより桁数が小さいもの
３：Nそのもの
その前に前計算パートで
memo[i][j]:=丁度j種類の並べ替えで作れる、サイズiの文字列の数
を求めておく。
１：Nと上からn桁は一致するNより小さいもの
上からn桁はNと一致するもの、n+1桁目はNのn+1桁目より、小さいものとして
ここまで使った文字数をusedと置くと
残りのN.size() - 1 - n桁を、必須要素のK-used種類と非必須要素のused種類で埋めればいいので
Σmemo[N.size() - 1 - n][K-used + i]*Binomial(16 - used , K-used) * Binomial(used , i)
(iは非必須要素から何種類を選択するか)
２：Nより桁数が小さいもの
Σmemo[i][K]*Binomial(16,K)*15/16;
15/16は0から始まるものを除外するため。
３：Nそのもの
これは上からsetで管理しておいてsetのサイズを見ればいい。
