結果
問題 | No.1848 Long Prefixes |
ユーザー |
👑 ![]() |
提出日時 | 2021-12-05 18:47:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,865 bytes |
コンパイル時間 | 1,951 ms |
コンパイル使用メモリ | 201,788 KB |
最終ジャッジ日時 | 2025-01-26 05:25:13 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 39 WA * 1 |
ソースコード
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #define _GLIBCXX_DEBUG using namespace std; using std::cout; using std::cin; using std::endl; using ll=long long; const ll mod=1e9+7; const ll mod_half=5e8+4; #define rep(i,a) for (ll i=0;i<a;i++) namespace po167{ //LCP vec[0,n) and vec[i,n) //for all i //O(vec.size()) template<class T> std::vector<int> Z_algo(std::vector<T> &vec){ int n=vec.size(); int ind=1,j=0,k; std::vector<int> ans(n,0); ans[0]=n; while(ind<n){ while(ind+j<n&&vec[j]==vec[ind+j]) j++; ans[ind]=j; if(j==0){ ind++; continue; } k=1; while(k+ind<n&&ans[k]+k<j){ ans[k+ind]=ans[k]; k++; } j-=k; ind+=k; } return ans; } std::vector<int> Z_algo(std::string &vec){ int n=vec.size(); int ind=1,j=0,k; std::vector<int> ans(n,0); ans[0]=n; while(ind<n){ while(ind+j<n&&vec[j]==vec[ind+j]) j++; ans[ind]=j; if(j==0){ ind++; continue; } k=1; while(k+ind<n&&ans[k]+k<j){ ans[k+ind]=ans[k]; k++; } j-=k; ind+=k; } return ans; } } using po167::Z_algo; // rainy ~ 雨に打たれて ~ int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin>>N; vector<ll> A(N+1); vector<ll> sum_A(N); rep(i,N){ cin>>A[i]; if(i) sum_A[i]=(sum_A[i-1]+A[i])%mod; else sum_A[i]=A[i]; } string S; cin>>S; assert(S.size()==N); S+="#"; vector<pair<char,ll>> p(N); rep(i,N-1){ p[i]={S[i+1],A[i+1]}; } auto z_val=Z_algo(p); ll ans=0; rep(i,N){ if(S[i]!=S[0]) continue; if(A[0]>A[i]){ ans+=((((A[i]+1)*A[i])%mod)*mod_half)%mod; ans%=mod; }else{ ans+=(((A[0]*(A[i]*2-A[0]+1))%mod)*mod_half)%mod; ans%=mod; if(i==0){ ans+=sum_A[N-1]-A[0]; ans%=mod; continue; } ans+=sum_A[z_val[i]]-A[0]; if(S[z_val[i]+1]==S[z_val[i]+1+i]){ ans+=min(A[z_val[i]+1],A[z_val[i]+i+1]); ans%=mod; } } } cout<<ans<<"\n"; }