| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 22323 | AcornCkiGs14004Team (#40) | Joyful KMP (KRIII5_JK) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef unsigned long long kriii;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
struct disj{
int pa[1000005];
void init(int n){
for(int i=0; i<=n; i++) pa[i] = i;
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
pa[q] = p; return 1;
}
}disj;
vector<int> gph[1000005];
vector<pi> v;
char str[1000005];
char rchr[1000005];
int fail[1000005];
kriii cnt[1000005];
lint k;
int n, deg[1000005];
int main(){
cin >> str >> k;
n = strlen(str);
disj.init(n);
int p = 0;
for(int i=1; str[i]; i++){
while(p > 0 && str[i] != str[p]){
v.push_back(pi(p, i));
p = fail[p];
}
if(str[i] == str[p]){
// printf("uni %d %d\n", i, p);
disj.uni(p, i);
p++;
}
else{
v.push_back(pi(p, i));
}
fail[i+1] = p;
}
for(auto &i : v){
i.first = disj.find(i.first);
i.second = disj.find(i.second);
if(i.first > i.second) swap(i.first, i.second);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
for(auto &i : v){
deg[i.second]++;
gph[i.second].push_back(i.first);
}
lint ans = 1;
for(int i=0; i<n; i++){
if(disj.find(i) == i){
ans *= max(0, 26 - deg[i]);
ans %= mod;
}
}
cout << ans << endl;
kriii tmp = 1;
for(int i=n-1; i>=0; i--){
if(disj.find(i) == i){
cnt[i] = tmp;
tmp = 0;
for(int j=0; j<26-deg[i]; j++){
tmp += cnt[i];
if(tmp > k) tmp = k+1;
}
}
}
if(tmp < k){
cout << "OVER";
return 0;
}
else{
k--;
for(int i=0; i<n; i++){
if(disj.find(i) == i){
lint x = k / cnt[i];
k -= x * cnt[i];
int mark[26] = {};
for(auto &j : gph[i]){
mark[rchr[j] - 'a'] = 1;
}
lint prvx = x;
for(int j=0; j<26; j++){
if(!mark[j]) x--;
if(x == -1){
rchr[i] = j + 'a';
break;
}
}
}
}
for(int i=0; i<n; i++) putchar(rchr[disj.find(i)]);
}
}