結果
問題 | No.2858 Make a Palindrome |
ユーザー |
![]() |
提出日時 | 2024-08-25 14:20:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 481 ms / 3,000 ms |
コード長 | 3,164 bytes |
コンパイル時間 | 4,372 ms |
コンパイル使用メモリ | 257,780 KB |
最終ジャッジ日時 | 2025-02-24 01:08:42 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 1000000000000000001struct rolling_hash{long long t_hash;static inline vector<long long> power;static const long long MOD = (1LL<<61)-1;static const long long b = 123456;int sz;rolling_hash(){sz = 0;t_hash = 0;}rolling_hash(char c){sz = 1;t_hash = b*c;}long long mul(__int128 x,__int128 y){__int128 t = x*y;t = (t>>61) + (t&MOD);if(t>=MOD)t -= MOD;return t;}long long get_pow(int sz){if(power.size()>sz)return power[sz];while(power.size()<=sz){if(power.size()==0)power.push_back(1);else power.push_back(mul(power.back(),b));}return power.back();}rolling_hash &operator+=(const rolling_hash &another){(*this).t_hash = mul((*this).t_hash,get_pow(another.sz));(*this).t_hash += another.t_hash;if((*this).t_hash>=MOD)(*this).t_hash -= MOD;(*this).sz += another.sz;return (*this);}rolling_hash operator+(const rolling_hash &another)const{return (rolling_hash(*this)+=another);}rolling_hash &operator-=(const rolling_hash &another){(*this).t_hash += MOD - mul(another.t_hash,get_pow((*this).sz-another.sz));if((*this).t_hash>=MOD)(*this).t_hash -= MOD;(*this).sz -= another.sz;return (*this);}rolling_hash operator-(const rolling_hash &another)const{return (rolling_hash(*this)-=another);}bool operator<(const rolling_hash &another)const{if((*this).t_hash!=another.t_hash)return (*this).t_hash<another.t_hash;return (*this).sz<another.sz;}bool operator==(const rolling_hash &another)const{return ((*this).t_hash==another.t_hash && (*this).sz==another.sz);}};void solve(){long long n,m;cin>>n>>m;string S;cin>>S;S = S+S+S+S;vector<rolling_hash> h(n*4+1), rh(n*4+1);//cout<<'a'<<endl;rep(i,n*4){h[i+1] = h[i]+rolling_hash(S[i]);rh[i+1] = rh[i]+rolling_hash(S[n*4-i-1]);}//cout<<'b'<<endl;long long ans = Inf64;rep(i,n){int ok = 0,ng = n+1;while(ng-ok>1){int mid = (ok+ng)/2;int l = n+i;int r = l+1;l -= mid,r += mid;if(h[r]-h[l]==rh[n*4-l]-rh[n*4-r])ok = mid;else ng = mid;}if(ok==n||ok*2+1 >= m){long long mm = m;if(mm%2==0)mm++;long long l = i - mm/2;long long r = l + mm;if(l<0){long long D =-l;D = (D+n-1)/n;l += D*n, r+=D*n;}ans = min((r+n-1)/n, ans);}}rep(i,n){if(S[i]!=S[i+1])continue;int ok = 0,ng = n+1;while(ng-ok>1){int mid = (ok+ng)/2;int l = n+i;int r = l+2;l -= mid,r += mid;if(h[r]-h[l]==rh[n*4-l]-rh[n*4-r])ok = mid;else ng = mid;}if(ok==n||ok*2+2 >= m){long long mm = m;if(mm%2==1)mm++;long long l = i - (mm-2)/2;long long r = l + mm;if(l<0){long long D =-l;D = (D+n-1)/n;l += D*n, r+=D*n;}ans = min((r+n-1)/n, ans);}}if(ans==Inf64)ans = -1;cout<<ans<<endl;}int main(){int _t;cin>>_t;rep(_,_t)solve();return 0;}