Submission #1235849

#TimeUsernameProblemLanguageResultExecution timeMemory
1235849shjeongJoyful KMP (KRIII5_JK)C++20
0 / 1
26 ms55624 KiB
#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(i,j), fail[i] = ++j; else adj[i].push_back(j), adj[j].push_back(i); } return fail; } ll ans = 1; bool vis[1010101]; void dfs(ll x){ ll c = 0; for(auto next : adj[x])c+=vis[next]; ans = ans*(26-c)%MOD; vis[x]=1; for(auto next : adj[x])if(!vis[next])dfs(next); } int main(){ fast; cin>>s>>k; n = sz(s); getfail(s); for(int i = 0 ; i < n ; i++){ for(auto j : adj[i])ADJ[uf.find(i)].push_back(uf.find(j)); } dfs(0); cout<<ans<<"\n"; cout<<"OVER\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...