Submission #373335

#	Time	Username	Problem	Language	Result	Execution time	Memory
373335		koioi.org-moonrabbit2	Joyful KMP (KRIII5_JK)	C++17	7 / 7	262 ms	88352 KiB

JK

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 l2;
//typedef long long l2;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<db,db,db> tdb;
typedef tuple<ll,ll,ll> tll;
typedef tuple<int,int,int,int> ti4;
typedef tuple<ll,ll,ll,ll> tl4;
typedef tuple<db,db,db,db> td4;
typedef vector<vector<ll>> mat;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //shuffle(a+1,a+1+n,rng)
uniform_int_distribution<> gen(1,100); //gen(rng)
//https://codeforces.com/contest/1264/submission/66344993 + 몇 가지 기능 직접 추가
ll modinv(ll a,ll m){
	if(m==1) return 0;
	a%=m;
	if(a<0) a+=m;
	if(a==1) return 1;
	return m-modinv(m,a)*m/a;
}
template <int MOD_> struct modnum{
private:
	int v;
public:
	static const int MOD = MOD_;
 
	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int () const { return v; }
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
	friend bool operator < (const modnum& a, const modnum& b) { return a.v < b.v; }
	friend bool operator <= (const modnum& a, const modnum& b) { return a.v <= b.v; }
	friend bool operator > (const modnum& a, const modnum& b) { return a.v > b.v; }
	friend bool operator >= (const modnum& a, const modnum& b) { return a.v >= b.v; }
 
	modnum operator ~ () const {
		modnum res;
		res.v = modinv(v, MOD);
		return res;
	}
 
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= (~o);
	}
 
	
	modnum operator-() const { return modnum(-v); }
	modnum& operator++() { return *this += 1; }
	modnum operator++(int){ modnum tmp=*this; ++*this; return tmp; }
	modnum& operator--() { return *this -= 1; }
	modnum operator--(int){ modnum tmp=*this; --*this; return tmp; }
 
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
	friend modnum pow(modnum a, ll p) {
		modnum ans = 1;
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	friend ostream& operator<<(std::ostream& os, const modnum& o)
	{
		os << o.v;
		return os;
	}
	friend istream& operator>>(std::istream& is, modnum& o)
	{
		is >> o.v;
		return is;
	}
};
const ll mod=1e9+7,inf=1e18;
using mi=modnum<1000000007>;
const int N=1e6+5,M=1e7+5;
string s;
int n,k,f[N],p[N],c[N],deg[N],m;
bool ok[30];
ll Q,sfx[N];
pii e[M];
mi ans=1;
vector<int> g[N];
int Find(int x){
    if(p[x]==x) return x;
    return p[x]=Find(p[x]);
}
void Union(int x,int y){
    x=Find(x); y=Find(y);
    if(x>y) swap(x,y);
    if(x<y) p[y]=x;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>s>>Q;
    n=s.size(); s="$"+s;
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=2;i<=n;i++){
        while(k&&s[k+1]!=s[i]){
            e[++m]=pii(k+1,i); k=f[k];
        }
        assert(k<i);
        if(s[k+1]==s[i]){
            k++;
            Union(k,i);
        }
        else e[++m]=pii(k+1,i);
        f[i]=k;
    }
    for(int i=1;i<=m;i++){
        e[i]=pii(Find(e[i].fi),Find(e[i].se));
        if(e[i].fi>e[i].se) swap(e[i].fi,e[i].se);
    }
    sort(e+1,e+1+m); m=unique(e+1,e+1+m)-e-1;
    for(int i=1;i<=m;i++){
        g[e[i].se].emplace_back(e[i].fi);
        deg[e[i].se]++;
    }
    sfx[n+1]=1;
    for(int i=n;i>=1;i--){
        sfx[i]=sfx[i+1];
        if(Find(i)==i){
            ans*=26-deg[i];
            if(sfx[i]!=-1&&sfx[i]<=Q/(26-deg[i])) sfx[i]*=26-deg[i];
            else sfx[i]=-1;
        }
    }
    cout<<ans<<"\n";
    if(sfx[1]!=-1&&Q!=ans){
        cout<<"OVER"; return 0;
    }
    for(int i=1;i<=26;i++) ok[i]=1;
    for(int i=1;i<=n;i++) if(Find(i)==i){
        for(int j : g[i]) ok[c[j]]=0;
        ll ret=1;
        if(sfx[i+1]!=-1){
            for(int j=1;j<=26;j++) if(sfx[i+1]<Q){
                Q-=sfx[i+1];
                ret++;
            }
        }
        for(int j=1;j<=26;j++) if(ok[j]){
            ret--;
            if(!ret){
                c[i]=j;
                break;
            }
        }
        for(int j : g[i]) ok[c[j]]=1;
    }
    for(int i=1;i<=n;i++) cout<<(char)('a'+c[Find(i)]-1);
	return 0;
}

• Subtask 1: 7 / 1