結果

問題 No.1018 suffixsuffixsuffix
ユーザー NyaanNyaanNyaanNyaan
提出日時 2020-04-03 22:14:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 20,917 bytes
コンパイル時間 2,653 ms
コンパイル使用メモリ 198,596 KB
実行使用メモリ 7,736 KB
最終ジャッジ日時 2024-07-03 03:34:14
合計ジャッジ時間 7,080 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 29 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#pragma region Tmpl
#include <bits/stdc++.h> // clang-format off
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define inc(...) char __VA_ARGS__; in(__VA_ARGS__)
#define in2(s,t) rep(i,sz(s)){in(s[i] , t[i]);}
#define in3(s,t,u) rep(i,sz(s)){in(s[i] , t[i] , u[i]);}
#define in4(s,t,u,v) rep(i,sz(s)){in(s[i] , t[i] , u[i] , v[i]);}
#ifdef ONLINE_JUDGE
#define rep(i,N) for(int i = 0; i < (int)(N); i++)
#define repr(i,N) for(int i = (int)(N) - 1; i >= 0; i--)
#define rep1(i,N) for(int i = 1; i <= (int)(N) ; i++)
#define repr1(i,N) for(int i = (N) ; (int)(i) > 0 ; i--)
#else
#define rep(i,N) for(long long i = 0; i < (long long)(N); i++)
#define repr(i,N) for(long long i = (long long)(N) - 1; i >= 0; i--)
#define rep1(i,N) for(long long i = 1; i <= (long long)(N) ; i++)
#define repr1(i,N) for(long long i = (N) ; (long long)(i) > 0 ; i--)
#endif
using namespace std; void solve();
using ll = long long; template<class T = ll> using V = vector<T>;
using vi = V<int>; using vl = V<>; using vvi = V< V<int> >;
using vd = V<double>; using vs = V<string>; using vvl = V< V<> >;
constexpr int inf = 1001001001; constexpr ll infLL = (1LL << 61) - 1;
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T,typename U>ll ceil(T a,U b){return (a + b - 1) / b;}
template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); for(int i=0;i<s;i++) os << (i ? " " : "") << v[i]
    ; return os; }
template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#ifdef NyaanDebug
#include "NyaanDebug.h"
#define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)
#define trca(v,N) do { cerr << #v << " = "; array_out(v , N);} while(0)
#define trcc(v) do { cerr << "name : " << #v << "\n"; int cnt = 0; each(x , v){cerr << (cnt++) << " : "; trc(x); } } while(0)
#else
#define trc(...)
#define trca(...)
#define trcc(...)
int main(){solve();}
#endif
constexpr ll TEN(int n){ll ret=1,x=10;while(n){if(n&1)ret*=x;x*=x;n>>=1;}return ret;}
#define mem(a, val) memset(a, val, sizeof(a))
#pragma endregion
struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7
    );} } iosetupnya;
using P = pair<int,int>; using vp = V<P>;
constexpr uint32_t MOD = /** 1000000007; //*/ 998244353; // clang-format on
////////////////////////////////////////////////////
// Suffix Array
//verify https://judge.yosupo.jp/submission/240
struct SuffixArray{
int _size;
vector<int> sa;
string &s;
SuffixArray(string &str):_size(str.size()) , s(str) {
// O( N logN )
s.push_back(0);
sa.resize(s.size());
iota(begin(sa), end(sa), 0);
sort(begin(sa), end(sa), [&](int a, int b) {
return s[a] == s[b] ? a > b : s[a] < s[b];
});
vector< int > classes(s.size()), c(s.begin(), s.end()), cnt(s.size());
for(int len = 1; len < (int)s.size(); len <<= 1) {
for(int i = 0; i < (int)s.size(); i++) {
if(i > 0 && c[sa[i - 1]] == c[sa[i]] && sa[i - 1] + len < (int)s.size() && c[sa[i - 1] + len / 2] == c[sa[i] + len / 2]) {
classes[sa[i]] = classes[sa[i - 1]];
} else {
classes[sa[i]] = i;
}
}
iota(begin(cnt), end(cnt), 0);
copy(begin(sa), end(sa), begin(c));
for(int i = 0; i < (int)s.size(); i++) {
int s1 = c[i] - len;
if(s1 >= 0) sa[cnt[classes[s1]]++] = s1;
}
classes.swap(c);
}
s.pop_back();
}
//
void output() {
cout << "SA\tidx\tstr" << endl;
for(int i = 0; i < size(); i++) {
cout << i << ": \t" << sa[i] << " \t" ;
if(sa[i] != _size) cout << s.substr(sa[i],_size - sa[i]) << endl;
else cout << "$" << endl;
}
cout << endl;
}
// sa.size()便
int size() const{return _size + 1;}
// sa[]便
int operator[](int k) const{return sa[k]; }
};
struct LCPArray {
const SuffixArray &SA;
vector<int> LCP, rank;
LCPArray(const SuffixArray &sa) : SA(sa) {
LCP.resize(SA.size()); rank.resize(SA.size());
//  ranksa
for(int i = 0; i < SA.size(); i++) {
rank[SA[i]] = i;
}
LCP[0] = 0;
//
for(int i = 0, h = 0; i < SA.size() - 1 ; i++) {
int j = SA[rank[i] - 1] ; h ? h-- : h;
// 使O(N)LCP
while( (i > j ? i : j) + h < SA.size() - 1 && SA.s[i + h] == SA.s[j + h] && ++h );
LCP[rank[i] - 1] = h;
}
}
//
void output() {
cout << "SA\tidx\tLCP\tstr" << endl;
for(int i = 0 ; i < SA.size() ; i++){
cout << i << "\t" << SA[i] <<" \t" << LCP[i] << "\t";
if(SA[i] == SA.size() - 1) cout << "$";
else cout << SA.s.substr(SA[i] , SA.size() - 1 - SA[i]);
cout << endl;
}
}
};
// Sparse Table
template<typename T>
struct SparseTable{
vector< vector< T > > table;
vector< int > log_table;
SparseTable(const vector< T > &v) {
int b = 0;
while((1 << b) <= (int)v.size()) ++b;
table.assign(b, vector< T >(1 << b));
for(int i = 0; i < (int)v.size(); i++) {
table[0][i] = v[i];
}
for(int i = 1; i < b; i++) {
for(int j = 0; j + (1 << i) <= (1 << b); j++) {
table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}
}
log_table.resize(v.size() + 1);
for(int i = 2; i < (int)log_table.size(); i++) {
log_table[i] = log_table[i >> 1] + 1;
}
}
// [l , r)
inline T query(int l, int r) {
int b = log_table[r - l];
return min(table[b][l], table[b][r - (1 << b)]);
}
};
// O(M + logN) O(N logN)
// verify
// https://onlinejudge.u-aizu.ac.jp/status/users/NyaanNyaan/submissions/1/ALDS1_14_D/judge/3874273/C++14
// https://atcoder.jp/contests/abc135/submissions/7574225
// https://judge.yosupo.jp/submission/241
// https://atcoder.jp/contests/abc141/submissions/7577295
struct StringSearch{
string &s;
const SuffixArray &sa;
const LCPArray &lcp;
SparseTable<int> sparse;
StringSearch(LCPArray &lcp)
: s(lcp.SA.s) , sa(lcp.SA) , lcp(lcp) , sparse(lcp.LCP){ }
// s[i , N)[j , N)
int ArbitaryLCP(int i , int j){
if(i == j) return (int)(s.size()) - i;
return sparse.query(
min(lcp.rank[i] , lcp.rank[j]) ,
max(lcp.rank[i] , lcp.rank[j])
);
}
pair<int,int> comp(const string &t , int len , int si , int ti = 0){
int sn = (int)s.size() , tn = (int) t.size();
si += len , ti += len;
while(si < sn && ti < tn){
if(s[si] != t[ti]) return make_pair( s[si]<t[ti] , ti);
si++ , ti++;
}
return make_pair( (si>=sn && ti<tn) , ti);
}
pair<int,int> find_range(int left , int med , int right , int len){
{
int ng = left - 1, ok = med;
while(ng + 1 < ok){
int cur = (ng + ok) / 2;
if(sparse.query(cur , med) >= len) ok = cur;
else ng = cur;
}
left = ok;
}
{
int ok = med , ng = right + 1;
while(ok + 1 < ng){
int cur = (ng + ok) / 2;
if(sparse.query(med, cur) >= len) ok = cur;
else ng = cur;
}
right = ok;
}
return make_pair(left , right);
}
// SA[left , right]
// -1
pair<int,int> find(string &t){
// [left , right]
// sa[0] left = 1
// len
int left = 1 , right = sa.size() - 1 , med = left;
int leftlen = 0 , rightlen = 0 , tlen = t.size();
pair<int,int> ret;
while(left + 1 < right){
med = (left + right) / 2;
int corres_len = max(
min(leftlen , sparse.query(left , med)) ,
min(rightlen, sparse.query(med , right))
);
if(corres_len < max(leftlen , rightlen)){
if(leftlen < rightlen)
left = med , leftlen = corres_len;
else
right= med ,rightlen = corres_len;
continue;
}
ret = comp(t , corres_len , sa[med]);
//trc(left,med,right,ret);
if(ret.second == tlen)
return find_range(left,med,right,tlen);
if(ret.first == 0)
right = med , rightlen = ret.second;
else
left = med , leftlen = ret.second;
}
if(sa.size() <= 3){
if(comp(t,0,sa[left]).second==tlen) return find_range(left,left,right,tlen);
if(comp(t,0,sa[right]).second==tlen) return find_range(left,right,right,tlen);
return make_pair(-1,-1);
}
med = left + right - med;
ret = comp(t , min(leftlen,rightlen) , sa[med]);
//trc(left,med,right,ret);
if(ret.second == tlen)
return find_range(left,med,right,tlen);
return make_pair(-1,-1);
}
};
// Suffix Array使(使)
// string
/*
SuffixArray sa(S);
LCPArray lcp(sa);
StringSearch search(lcp);
*/
// 使
// Roriha s_rori(S);
// RollingHash<vector<int>> vrori(v);
template<typename string_t> struct RollingHash{
using ull = unsigned long long;
using Pu = pair<ull , ull>;
string_t& data;
vector<Pu> hashed , power;
int size_;
static Pu basis;
static constexpr ull rmod = (1ull << 61) - 1;
static constexpr ull mul(const ull a,const ull b){
ull l1 = (uint32_t)a, h1 = a>>32, l2 = (uint32_t)b, h2 = b>>32;
ull l = l1*l2, m = l1*h2 + l2*h1, h = h1*h2;
ull ret = (l & rmod) + (l>>61) + (h << 3) + (m >> 29) + (m << 35 >> 3);
if(ret > rmod) ret = (ret & rmod) + (ret>>61);
if(ret >= rmod) ret -= rmod;
return ret;
}
static constexpr ull mul_plus(const ull a,const ull b,const ull c){
ull l1 = (uint32_t)a, h1 = a>>32, l2 = (uint32_t)b, h2 = b>>32;
ull l = l1*l2, m = l1*h2 + l2*h1, h = h1*h2;
ull ret = (l & rmod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + c;
if(ret > rmod) ret = (ret & rmod) + (ret>>61);
if(ret >= rmod) ret -= rmod;
return ret;
}
static constexpr ull modpow(ull a,ull b){
a %= rmod;
ull r = 1;
while(b) {
if(b & 1) r = mul(r , a);
a = mul(a , a);
b >>= 1;
}
return r;
}
static constexpr bool isPrimitive(ull x, vector<ull> &ds) {
for(ll d : ds)
if(d != rmod - 1) {
if(modpow( x, (rmod - 1) / d ) == 1) return false;
}
return true;
}
static constexpr Pu get_basis(){
vector<ull> ds = {2,3,5,7,11,13,31,41,61,151,331,1321};
auto rand_time = chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count();
mt19937_64 rng(rand_time);
ull a = -1 , b = -1;
do{ a = rng() % rmod; }while(isPrimitive(a , ds) == false);
do{ b = rng() % rmod; }while(a == b || isPrimitive(b , ds) == false);
return Pu(a , b);
}
// Rolling Hash O( |S| )
RollingHash(string_t &S) : data(S) , size_((int)S.size()){
// hashed[i] [0 , i) hashed[0] = (0,0)
// power[i] basisi
hashed.resize(size_ + 1);
power.resize(size_ + 1);
power[0] = Pu(1 , 1); hashed[0] = Pu(0 , 0);
for(int i = 1 ; i <= size_ ; i++ ){
power[i].fi = mul( power[i - 1].fi , basis.fi);
power[i].se = mul( power[i - 1].se , basis.se);
hashed[i].fi = mul_plus( hashed[i - 1].fi , basis.fi , S[i - 1]);
hashed[i].se = mul_plus( hashed[i - 1].se , basis.se , S[i - 1]);
}
}
// [ l , r ) O(1)
Pu get(const int l , const int r){
Pu ret;
ret.fi = rmod - mul_plus( hashed[l].fi , power[r-l].fi , rmod - hashed[r].fi );
ret.se = rmod - mul_plus( hashed[l].se , power[r-l].se , rmod - hashed[r].se );
return ret;
}
//  O( |T| )
Pu get_hash(string_t &T){
Pu ret = Pu(0 , 0);
for(int i = 0 ; i < (int)T.size() ; i++){
ret.fi = mul_plus(ret.fi , basis.fi , T[i]);
ret.se = mul_plus(ret.se , basis.se , T[i]);
}
return ret;
}
// O ( |S| + |T| )
// -1
int find(string_t &T){
auto t_hash = get_hash(T);
int t_size = (int)(T.size());
// |S| < |T|for
for(int i = 0 ; i <= size_ - t_size ; i++){
if(t_hash == get( i , i + t_size ) ) return i;
}
return -1;
}
// O ( |S| + |T| )
// index
vector<int> find_all(string_t &T){
auto t_hash = get_hash(T);
int t_size = (int)(T.size());
vector<int> ret;
// |S| < |T|for
for(int i = 0 ; i <= size_ - t_size ; i++){
if(t_hash == get( i , i + t_size ) ) ret.push_back(i);
}
return ret;
}
// Longest Common Prefix() O( log |S| )
// S[al , ar)T[bl , br)
// (T , Sa , Tb)
//  
int LongestCommonPrefix(RollingHash<string_t> &t , int al , int bl , int ar = -1 , int br = -1){
if(ar == -1) ar = size_;
if(br == -1) br = t.size_;
int ok = 0 , ng = min(ar - al , br - bl) + 1;
while(ok + 1 < ng){
int med = (ok + ng) / 2;
if( get(al , med + al) == t.get(bl , med + bl) ) ok = med;
else ng = med;
}
return ok;
}
// O( log |S + T| ) 
// S[al , ar)T[bl , br)
// 1 S 0 -1 T
int strcmp(RollingHash<string_t> &t , int al , int bl , int ar = -1 , int br = -1){
if(ar == -1) ar = size_;
if(br == -1) br = t.size_;
int n = LongestCommonPrefix(t , al , bl , ar , br);
if(al + n == ar)
return (bl + n == br) ? 0 : 1;
else if(bl + n == br)
return -1;
else return ( data[al + n] < t.data[bl + n] ) ? 1 : -1;
}
// O ( |S| (log|S|)^2 )
int LongestCommonSubString(){
auto func = [&](int len) -> bool {
map < Pu , int > m;
for(int i = 0 ; i <= size_ - len ; i++){
if( (m[get(i , i + len)] += 1) != 1) return true;
}
return false;
};
int ok = 0 , ng = size_ ;
while(ok + 1 < ng){
int med = (ok + ng) / 2;
if(func(med)) ok = med;
else ng = med;
}
return ok;
}
};
//
template<typename T> pair<unsigned long long,unsigned long long> RollingHash<T>::basis = RollingHash<T>::get_basis();
using Roriha = RollingHash<string>;
// Prime -> 1 {0, 0, 1, 1, 0, 1, 0, 1, ...}
vector<int> Primes(int N) {
vector<int> A(N + 1, 1);
A[0] = A[1] = 0;
for (int i = 2; i * i <= N; i++)
if (A[i] == 1)
for (int j = i << 1; j <= N; j += i) A[j] = 0;
return A;
}
// Prime Sieve {2, 3, 5, 7, 11, 13, 17, ...}
vector<long long> PrimeSieve(int N) {
vector<int> prime = Primes(N);
vector<long long> ret;
for (int i = 0; i < (int)prime.size(); i++)
if (prime[i] == 1) ret.push_back(i);
return ret;
}
// Factors (using for fast factorization)
// {0, 0, 1, 1, 2, 1, 2, 1, 2, 3, ...}
vector<int> Factors(int N) {
vector<int> A(N + 1, 1);
A[0] = A[1] = 0;
for (int i = 2; i * i <= N; i++)
if (A[i] == 1)
for (int j = i << 1; j <= N; j += i) A[j] = i;
return A;
}
// totient function φ(N)=(1 ~ N , gcd(i,N) = 1)
// {0, 1, 1, 2, 4, 2, 6, 4, ... }
vector<int> EulersTotientFunction(int N) {
vector<int> ret(N + 1, 0);
for (int i = 0; i <= N; i++) ret[i] = i;
for (int i = 2; i <= N; i++) {
if (ret[i] == i)
for (int j = i; j <= N; j += i) ret[j] = ret[j] / i * (i - 1);
}
return ret;
}
// Divisor ex) 12 -> {1, 2, 3, 4, 6, 12}
vector<long long> Divisor(long long N) {
vector<long long> v;
for (long long i = 1; i * i <= N; i++) {
if (N % i == 0) {
v.push_back(i);
if (i * i != N) v.push_back(N / i);
}
}
return v;
}
// Factorization
// ex) 18 -> { (2,1) , (3,2) }
vector<pair<long long, int> > PrimeFactors(long long N) {
vector<pair<long long, int> > ret;
for (long long p = 2; p * p <= N; p++)
if (N % p == 0) {
ret.emplace_back(p, 0);
while (N % p == 0) N /= p, ret.back().second++;
}
if (N >= 2) ret.emplace_back(N, 1);
return ret;
}
// Factorization with Prime Sieve
// ex) 18 -> { (2,1) , (3,2) }
vector<pair<long long, int> > PrimeFactors(long long N,
const vector<long long> &prime) {
vector<pair<long long, int> > ret;
for (auto &p : prime) {
if (p * p > N) break;
if (N % p == 0) {
ret.emplace_back(p, 0);
while (N % p == 0) N /= p, ret.back().second++;
}
}
if (N >= 2) ret.emplace_back(N, 1);
return ret;
}
// modpow for mod < 2 ^ 31
long long modpow(long long a, long long n, long long mod) {
a %= mod;
long long ret = 1;
while (n > 0) {
if (n & 1) ret = ret * a % mod;
a = a * a % mod;
n >>= 1;
}
return ret % mod;
};
// Check if r is Primitive Root
bool isPrimitiveRoot(long long r, long long mod) {
r %= mod;
if (r == 0) return false;
auto pf = PrimeFactors(mod - 1);
for (auto &x : pf) {
if (modpow(r, (mod - 1) / x.first, mod) == 1) return false;
}
return true;
}
// Get Primitive Root
long long PrimitiveRoot(long long mod) {
long long ret = 1;
while (isPrimitiveRoot(ret, mod) == false) ret++;
return ret;
}
// Extended Euclidean algorithm
// solve : ax + by = gcd(a, b)
long long extgcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long d = extgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
// Check if n is Square Number
bool isSquare(ll n) {
if(n == 0 || n == 1) return true;
ll d = (ll)sqrt(n) - 1;
while (d * d < n) ++d;
return d * d == n;
}
// return a number of n's digit
// zero ... return value if n = 0 (default -> 1)
int isDigit(ll n, int zero = 1) {
if (n == 0) return zero;
int ret = 0;
while (n) {
n /= 10;
ret++;
}
return ret;
}
void solve(){
inl(N,M,Q);
ins(S);
vl K(Q); in(K);
//
if(M == 1){
SuffixArray sa(S);
vi ans(Q);
rep(i,Q){
ans[i] = sa.sa[K[i]] + 1;
}
out(ans);
exit(0);
}
//
{
Roriha rori(S);
auto ds = Divisor(N);
each(d,ds){
int ok = 1;
auto ide = rori.get(0,d);
for(int i = 0 ; i < N ; i += d){
if(rori.get(i,i+d) != ide){
ok = 0; break;
}
}
if(ok){
S = S.substr(0,d);
M *= (N / d);
N = d;
break;
}
}
}
S += S;
SuffixArray sa(S);
//
vl ans(Q);
ll ki = 0;
ll cur = 1;
each(x , sa.sa){
if(ki == Q) break;
if(x == sz(S)) continue;
// cur
// nxt
ll nxt;
//
if(x >= N) nxt = cur + 1;
//
else nxt = cur + M - 1;
while(ki != Q && K[ki] < nxt){
if(x >= N) ans[ki] = N * M - 2 * N + x + 1;
// cur N*M - 2 * N + x + 1
// 1N退
else ans[ki] = N*M - 2*N + x + 1 - (K[ki]-cur)*N;
ki++;
}
cur = nxt;
}
out(ans);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0