2012-C08-team5-problem-B

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <string>
#include <vector>
using namespace std;

const long long INF = 1ll<<60;

long long MUL(long long x, long long y){
    return __builtin_clzll(x)+__builtin_clzll(y)<=64?INF:x*y;
}
long long ADD(long long x, long long y){
    return x=x+y>INF?INF:x+y;
}

int main(){
    int n,m;
    long long idx,cnt[2205]={1},pfx[2205]={1};
    char str[205];
    string a[100],ans;
    vector<int> u[100],v[100];
    sscanf(gets(str),"%d%d%lld",&n,&m,&idx); idx--;
    for(int i=0;i<n;i++) a[i]=gets(str);
    for(int i=0;i<m;i++) for(int j=0;j<n;j++)
        cnt[i+a[j].size()]=ADD(cnt[i+a[j].size()],cnt[i]);
    if(idx>=cnt[m]) return puts("-"),0;
    for(int i=0;i<n;i++) if(a[i].size()<=m) u[i].push_back(0);
    for(int l=0;l<m;l++){
        long long use[128]={};
        for(int i=0;i<n;i++){
            for(size_t j=0;j<u[i].size();j++){
                int x=u[i][j];
                long long p=pfx[l-x],q=cnt[m-l+x-a[i].size()];
                use[int(a[i][x])]=ADD(use[int(a[i][x])],MUL(p,q));
            }
        }
        int c,start=0;
        for(c='a';use[c]<=idx;idx-=use[c++]);
        ans+=char(c);
        for(int i=0;i<n;i++){
            for(size_t j=0;j<u[i].size();j++){
                int x=u[i][j];
                if(c==a[i][x] && a[i].size()!=x+1) v[i].push_back(x+1);
                if(c==a[i][x] && a[i].size()==x+1){
                    pfx[l+1]=ADD(pfx[l+1],pfx[l-x]);
                    start=1;
                }
            }
        }
        for(int i=0;i<n;v[i++].clear()){
            if(start && l+a[i].size()<m) v[i].push_back(0);
            u[i].swap(v[i]);
        }
    }
    puts(ans.c_str());
}
}}}

#include <cstdio>
#include <string>
#include <vector>
using namespace std;
const long long INF = 1ll<<60;
long long MUL(long long x, long long y){
    return __builtin_clzll(x)+__builtin_clzll(y)<=64?INF:x*y;
}
long long ADD(long long x, long long y){
    return x=x+y>INF?INF:x+y;
}
int main(){
    int n,m;
    long long idx,cnt[2205]={1},pfx[2205]={1};
    char str[205];
    string a[100],ans;
    vector<int> u[100],v[100];
    sscanf(gets(str),"%d%d%lld",&n,&m,&idx); idx--;
    for(int i=0;i<n;i++) a[i]=gets(str);
    for(int i=0;i<m;i++) for(int j=0;j<n;j++)
        cnt[i+a[j].size()]=ADD(cnt[i+a[j].size()],cnt[i]);
    if(idx>=cnt[m]) return puts("-"),0;
    for(int i=0;i<n;i++) if(a[i].size()<=m) u[i].push_back(0);
    for(int l=0;l<m;l++){
        long long use[128]={};
        for(int i=0;i<n;i++){
            for(size_t j=0;j<u[i].size();j++){
                int x=u[i][j];
                long long p=pfx[l-x],q=cnt[m-l+x-a[i].size()];
                use[int(a[i][x])]=ADD(use[int(a[i][x])],MUL(p,q));
            }
        }
        int c,start=0;
        for(c='a';use[c]<=idx;idx-=use[c++]);
        ans+=char(c);
        for(int i=0;i<n;i++){
            for(size_t j=0;j<u[i].size();j++){
                int x=u[i][j];
                if(c==a[i][x] && a[i].size()!=x+1) v[i].push_back(x+1);
                if(c==a[i][x] && a[i].size()==x+1){
                    pfx[l+1]=ADD(pfx[l+1],pfx[l-x]);
                    start=1;
                }
            }
        }
        for(int i=0;i<n;v[i++].clear()){
            if(start && l+a[i].size()<m) v[i].push_back(0);
            u[i].swap(v[i]);
        }
    }
    puts(ans.c_str());
}