結果

問題 No.2858 Make a Palindrome
ユーザー 0214sh70214sh7
提出日時 2024-08-25 15:44:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,372 bytes
コンパイル時間 2,727 ms
コンパイル使用メモリ 218,096 KB
実行使用メモリ 33,260 KB
最終ジャッジ日時 2024-08-25 15:44:34
合計ジャッジ時間 15,070 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,170 ms
6,812 KB
testcase_01 AC 459 ms
6,944 KB
testcase_02 AC 444 ms
6,944 KB
testcase_03 AC 449 ms
6,944 KB
testcase_04 AC 475 ms
6,940 KB
testcase_05 AC 366 ms
6,940 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 281 ms
6,940 KB
testcase_14 WA -
testcase_15 AC 88 ms
6,940 KB
testcase_16 AC 83 ms
6,944 KB
testcase_17 AC 90 ms
6,940 KB
testcase_18 AC 85 ms
6,940 KB
testcase_19 AC 88 ms
6,944 KB
testcase_20 AC 78 ms
29,336 KB
testcase_21 AC 77 ms
30,140 KB
testcase_22 AC 47 ms
17,344 KB
testcase_23 AC 95 ms
30,732 KB
testcase_24 AC 63 ms
26,384 KB
testcase_25 AC 61 ms
23,508 KB
testcase_26 AC 72 ms
23,336 KB
testcase_27 AC 88 ms
32,752 KB
testcase_28 AC 73 ms
24,828 KB
testcase_29 AC 103 ms
31,904 KB
testcase_30 AC 86 ms
33,136 KB
testcase_31 AC 88 ms
33,096 KB
testcase_32 AC 82 ms
33,248 KB
testcase_33 AC 87 ms
33,132 KB
testcase_34 AC 89 ms
33,140 KB
testcase_35 AC 86 ms
33,260 KB
testcase_36 AC 81 ms
33,100 KB
testcase_37 AC 84 ms
33,136 KB
testcase_38 AC 87 ms
33,136 KB
testcase_39 AC 84 ms
33,188 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> PP;
// #define MOD 1000000007
#define MOD 998244353
#define INF 2305843009213693951
//#define INF 810114514
#define PI 3.141592653589
#define setdouble setprecision
#define REP(i,n) for(ll i=0;i<(n);++i)
#define OREP(i,n) for(ll i=1;i<=(n);++i)
#define RREP(i,n) for(ll i=(n)-1;i>=0;--i)
#define ORREP(i,n) for(ll i=(n);i>=1;--i)
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define GOODBYE do { cout << "-1" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug true
#define debug2 false

class rollinghash{
    // Copyright (c) 2023 0214sh7
    // https://github.com/0214sh7/library/
    private:
    static constexpr long long mod = (1LL << 61)-1;
    std::vector<long long> Base = {12345,10000000};
    std::vector<long long> BaseInv;
    std::vector<std::vector<long long>> BaseInvExp;
    static constexpr long long h = 100;
    
    long long product(long long a,long long b){
        static constexpr long long m = 1LL << 31;
        long long a1 = a/m,a2 = a%m;
        long long b1 = b/m,b2 = b%m;
        
        long long r = 0 , s;
        r = (r + 2*a1*b1) % mod;
        s = (a1*b2 + b1*a2) % mod;
        long long s1 = s/m,s2 = s%m;
        s = (2*s1+m*s2) % mod;
        r = (r + s) % mod;
        r = (r + a2*b2) % mod;
        
        return r;
    }
    
    long long power(long long b,long long e){
        long long r=1;
        while(e){
            if(e&1){
                r=product(r,b)%mod;
            }
                b=product(b,b)%mod;
                e >>=1;
        }
        return r;
    }
    
    public:
    std::vector<long long> S;
    std::vector<std::vector<long long>> H,Hsum;
    
    void init(std::vector<long long> cs){
        S=cs;
        int n=S.size();
        
        BaseInv.resize(Base.size());
        BaseInvExp.resize(Base.size());
        H.resize(Base.size());
        Hsum.resize(Base.size());
        for(int i=0;i<(int)Base.size();i++){
            BaseInvExp[i].assign(n+1,1);
            H[i].assign(n+1,0);
            Hsum[i].assign(n+1,0);
        }
        
        //逆元
        for(int i=0;i<(int)Base.size();i++){
            BaseInv[i]=power(Base[i],mod-2);
        }
        for(int i=0;i<(int)Base.size();i++){
            for(int j=0;j<n;j++){
                BaseInvExp[i][j+1] = product(BaseInvExp[i][j],BaseInv[i]);
            }
        }
        
        //本体
        for(int i=0;i<(int)Base.size();i++){
            long long b=1;
            for(int j=0;j<n;j++){
                H[i][j]=product(b,S[j]+h);
                b=product(b,Base[i]);
            }
        }
        
        //累積和
        for(int i=0;i<(int)Base.size();i++){
            for(int j=0;j<n;j++){
                Hsum[i][j+1]=(Hsum[i][j]+H[i][j])%mod;
            }
        }
    }
    
    rollinghash(std::vector<long long> C){
        init(C);
    }
    
    std::vector<long long> get(int l,int r){
        std::vector<long long> R(Base.size());
        for(int i=0;i<(int)Base.size();i++){
            long long g = (Hsum[i][r]-Hsum[i][l]+mod)%mod;
            g=product(g,BaseInvExp[i][l]);
            R[i] = g;
        }
        return R;
    }
    
    std::vector<long long> instant(std::vector<long long> P){
        std::vector<long long> R;
        for(int i=0;i<(int)Base.size();i++){
            long long r = 0, b = 1;
            for(int j=0;j<(int)P.size();j++){
                r = (r+product(b,P[j]+h))%mod;
                b = product(b,Base[i]);
            }
            R.push_back(r);
        }
        return R;
    }
    
    std::vector<long long> connect(std::vector<long long> P,long long ps,std::vector<long long> Q,long long qs){
        std::vector<long long> R;
        for(int i=0;i<(int)Base.size();i++){
            long long r = (product(Q[i],power(Base[i],ps))+P[i])%mod;
            R.push_back(r);
        }
        return R;
        assert(qs==qs);
    }
    
};

ll Manacher(string _s){
    
    
    int n = _s.size();
  //'#'の追加
  string s(2 * n + 1, '#');
  for (int i = 0; i < n; i++) s[2 * i + 1] = _s[i];
  n = 2 * n + 1;
  
//   cout << "? " << s << endl;

  vector<int> rad(n);
  int c = 0, r = 0;

  while (c < n) {
    // cを中心に同じ文字がどこまで連続するか
    while (0 <= c - r && c + r < n && s[c - r] == s[c + r]) r++;
    rad[c] = r;

    //回文の長さに応じて利用可能な範囲を確認しつつメモ
    int k = 1;
    while (0 <= c - k && k + rad[c - k] < r) {
      rad[c + k] = rad[c - k];
      k++;
    }
    //すでに計算が終わった分だけ中心と探索半径をずらす
    c += k;
    r -= k;
  }
  //'＃'分の補正
//   for (int i = 0; i < n; i++) {
//     if (i % 2 == 0)
//       rad[i] = (rad[i] - 1) / 2;
//     else
//       rad[i] /= 2;
//   }
  
//   REP(i,rad.size()){cout << rad[i] << " ";}cout << endl;
  ll Lmax = 0;
  REP(i,rad.size()){
      if(i%2==0){
        Lmax = max(Lmax,(ll)rad[i]-1);
      }else{
          Lmax = max(Lmax,(ll)rad[i]-1);
      }
      
  }
//   cout << "! " << Lmax << endl;
  return Lmax;
    
}

void solve(){
    
    ll N,X;
    cin >> N >> X;
    string S;
    cin >> S;
    vector<ll> Ss(N);
    REP(i,N){Ss[i] = S[i];}
    
    rollinghash rolS(Ss);
    reverse(ALL(Ss));
    rollinghash rolR(Ss);
    
    // 1個のなかにあるか？
    ll L = Manacher(S);
    if(L >= X){
        cout << 1 << endl;
        return;
    }
    
    // 2個のなかにあるか？
    string T = S+S;
    L = Manacher(T);
    if(L >= X){
        cout << 2 << endl;
        return;
    }
    
    // 回文か？
    if(rolS.get(0,N)==rolR.get(0,N)){
        
        cout << (X+N-1)/N << endl;
        return;
        
    }
    
    // 2-回文か？
    REP(i,N-1){
        if(rolS.get(0,i+1)==rolR.get(N-i-1,N) && rolS.get(i+1,N)==rolR.get(0,N-i-1)){
            
            ll c = max(i+1,N-i-1);
            ll Ans = 1, t = max(0ll,X-c);
            Ans += (t+N-1)/N;
            cout << Ans << endl;
            return;
            
        }
    }
    
    cout << -1 << endl;
    return;
    
}

int main(void){
    //cin.tie(nullptr);
    //ios::sync_with_stdio(false);
    
    ll T;
    cin >> T;
    REP(_,T){solve();}
    
    return 0;
    
}
0