Kth Sentence (AOJ 2341)

AOJ Online Judge

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2341

問題

単語がn個ある。その単語を重複有りで並べ替えて出来るm文字の文字列でk番目のものを答えよ。ただし、使う単語の順番が異なった場合それは違う文字列とみなす。
1<=n<=100
1<=m<=2000
1<=k<=10^18

解法

解説通りにx文字で作れる文字列の総数を前計算しておいて、1文字ずつ決めながらDPすれば良い。接尾辞が同じ文字列になるかどうかの判定は、ちゃんと答えの方の末尾の文字を単語の端に合わせつつ計算しないと26倍遅くなってTLEする。また接尾辞を比較する際に文字数を増やすと答えの方は左から、単語の方は右から文字を追加することになるので、こちらもちゃんとローリングハッシュを使っておかないとTLEする。