Kth Sentence (AOJ2341)

500点

問題:
lowercaseからなる文字列(長さ200まで)がN(<=100)個与えられる.これを並べて(それぞれ複数回使っても良いし,一回も使わなくても良い)できる長さM(<=2000)の文字列のうち,辞書順K(<=1e18)個めのものを求めよ.

解答:
aから始まるのは何通り?
bから・・・みたいなのをやって,どれから始まるか特定する.その後もcaから,cbから・・・みたいなのをやってく.
例えばacbまでは確定してて,acba,acbb...と調べるためには,acbのbがどこ由来のやつ(の右を考慮してない並べ方)が何通りあるか?というのを持っとけば良い.例えばac bdみたいに並べられてるんだったら次はdしかない, acb とか a cbみたいに並べられてるんだったら,次は好きな文字列が置ける."どこ由来"は「文字列iの長さjのところ」みたいなのを持てばいい.それらが分かってたら,遷移はさっき言ったとおりで,実際に何通りか数えるには,way[i]=長さiの文字列を作る方法 みたいなのを前計算しといて,way[後何文字埋めればいいか]をそれぞれに対しかければいい.
オーバーフロー:
足し算,かけざんがK以上にならないようにする(ab>c⇔a>c/b ただし切り捨て割り算 a,b,c>0)

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
int N,L;
ll K;
void add(ll &x,ll y){
	x=min(x+y,K);
}
ll pro(ll x,ll y){
	if(x==0||y==0) return 0;
	if(x>K/y) return K;
	return x*y;
}
string s[100];
int n[100];
ll way_[2400];
ll *way=way_+300;
ll dp[100][200];
int main(){
	cin>>N>>L>>K;
	rep(i,N) cin>>s[i];
	rep(i,N) n[i]=s[i].size();
	way[0]=1;
	rep(i,L){
		rep(j,N) if(i+n[j]<=L) add(way[i+n[j]],way[i]);
	}
	string ans;
	dp[0][n[0]-1]=1;
	rep(i,L){
		ll nx[26]={};
		rep(j,N){
			rep(k,n[j]){
				if(k==n[j]-1){
					rep(l,N) add(nx[s[l][0]-'a'],pro(dp[j][k],way[L-i-n[l]]));
				}else{
					add(nx[s[j][k+1]-'a'],pro(dp[j][k],way[L-i-n[j]+k+1]));
				}
			}
		}
		ll sum=0;
		int A=-1;
		rep(j,26){
			ll tmp=sum;
			sum+=nx[j];
			if(sum>=K){
				K-=tmp;
				A=j;
				break;
			}
		}
		if(A<0){
			assert(i==0);
			puts("-");
			return 0;
		}
		ans+='a'+A;
		ll ndp[100][200]={};
		rep(j,N){
			rep(k,n[j]){
				if(k==n[j]-1){
					rep(l,N) if(s[l][0]-'a'==A) add(ndp[l][0],dp[j][k]);
				}else{
					if(s[j][k+1]-'a'==A) add(ndp[j][k+1],dp[j][k]);
				}
			}
		}
		rep(j,N) rep(k,n[j]) dp[j][k]=ndp[j][k];
	}
	cout<<ans<<endl;
}