Submission #1235893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235893		shjeong	Joyful KMP (KRIII5_JK)	C++20	7 / 1	174 ms	134604 KiB

JK

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define COMP(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define MOD2 998244353
#define sz(x) (ll)x.size()
typedef __int128_t lll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ll, pll> PP;
const ll Lnf = 2e9;
ll n, k;
string s;
struct UF{
    vector<ll> p;
    UF(): p(1010101,-1){}
    ll find(ll x){ if(p[x]<0)return x; return p[x] = find(p[x]); }
    void merge(ll x, ll y){
        x=find(x),y=find(y);
        if(x==y)return; p[x]+=p[y]; p[y]=x;
    }
} uf;
vector<ll> adj[1010101], ADJ[1010101];
vector<ll> getfail(string &s){
    ll n = sz(s);
    vector<ll> fail(n);
    for(int i = 1, j = 0 ; i < n ; i++){
        while(j>0 and s[i]^s[j]){
            adj[i].push_back(j); adj[j].push_back(i);
            j=fail[j-1];
        }
        if(s[i]==s[j])uf.merge(j,i), fail[i] = ++j;
        else adj[i].push_back(j), adj[j].push_back(i);
    }
    return fail;
}
ll ans = 1;
bool vis[1010101];
char res[1010101];
ll dp[1010101];
void dfs(ll x){
    ll c = sz(ADJ[x]);
    ans = ans*(26-c)%MOD;
    dp[x]=26-c;
}
void go(ll x){
    ll b = 0;
    for(auto next : ADJ[x]){
        b |= (1<<(res[next]-'a'));
    }
    for(int i = 0 ; i < 26 ; i++)if(~b&(1<<i)){
        res[x] = char(i+'a');
        if(k>dp[x])k -= dp[x];
        else break;
    }
//    cout<<x<<" "<<dp[x]<<" "<<k<<" "<<res[x]<<endl;
}
int main(){
    fast;
    cin>>s>>k; n = sz(s);
    getfail(s);
    for(int i = 0 ; i < n ; i++){
        for(auto j : adj[i])if(uf.find(i) > uf.find(j))ADJ[uf.find(i)].push_back(uf.find(j));
    }
    for(int i = 0 ; i < n ; i++)sort(all(ADJ[i])), COMP(ADJ[i]);
    for(int i = 0 ; i < n ; i++)if(i==uf.find(i))dfs(i);
    ll prv = 1;
    for(int i = n-1 ; i >= 0 ; i--)if(i==uf.find(i)){
        ll p = prv;
        if((lll)prv*dp[i] > LLONG_MAX)prv = LLONG_MAX;
        else prv*=dp[i];
        dp[i] = p;
    }
    cout<<ans<<"\n";
    if((lll)dp[0]*26 < k)return !(cout<<"OVER");
    for(int i = 0 ; i < n ; i++)if(i==uf.find(i))go(i);
    for(int i = 0 ; i < n ; i++)cout<<res[uf.find(i)];
}

• Subtask 1: 7 / 1