結果

問題 No.2858 Make a Palindrome
ユーザー 0214sh70214sh7
提出日時 2024-08-25 14:58:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,942 bytes
コンパイル時間 2,397 ms
コンパイル使用メモリ 215,460 KB
実行使用メモリ 30,064 KB
最終ジャッジ日時 2024-08-25 14:58:56
合計ジャッジ時間 14,268 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,102 ms
6,816 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 264 ms
6,940 KB
testcase_14 WA -
testcase_15 AC 79 ms
6,940 KB
testcase_16 AC 83 ms
6,940 KB
testcase_17 AC 82 ms
6,940 KB
testcase_18 AC 82 ms
6,940 KB
testcase_19 AC 86 ms
6,944 KB
testcase_20 AC 73 ms
26,524 KB
testcase_21 AC 69 ms
27,324 KB
testcase_22 AC 41 ms
15,684 KB
testcase_23 AC 89 ms
26,520 KB
testcase_24 AC 59 ms
23,828 KB
testcase_25 AC 57 ms
21,328 KB
testcase_26 AC 64 ms
20,396 KB
testcase_27 AC 79 ms
29,808 KB
testcase_28 AC 64 ms
22,400 KB
testcase_29 AC 88 ms
27,680 KB
testcase_30 AC 77 ms
29,940 KB
testcase_31 AC 80 ms
29,936 KB
testcase_32 AC 75 ms
29,936 KB
testcase_33 AC 81 ms
30,064 KB
testcase_34 AC 84 ms
29,940 KB
testcase_35 AC 80 ms
29,932 KB
testcase_36 AC 77 ms
29,936 KB
testcase_37 AC 80 ms
29,940 KB
testcase_38 AC 81 ms
30,064 KB
testcase_39 AC 73 ms
29,936 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);
    }
    
};

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);
    
    // 回文か？
    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