# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1097275 | 2024-10-06T16:00:00 Z | vjudge1 | Palindromic Partitions (CEOI17_palindromic) | C++17 | 1 ms | 348 KB |
#include <bits/stdc++.h> using namespace std; #define int long long const int mod = 1e9 + 7; const int p = 41; int binpow(int a,int b){ if(!b)return 1; int res = binpow(a,b/2); res = (res * res) % mod; if(b&1)res = (res * a) % mod; return res; } void solve(){ string s; cin >> s; int n = s.size(); s = "." + s; vector<int> pi(n+1,1),res(n+1,0); for(int i=1;i<=n;++i){ pi[i] = pi[i-1] * p % mod; res[i] = res[i-1] + ((pi[i] * (s[i] - 'a' + 1)) % mod); res[i] %= mod; } int l=0,r=n; int cnt = 1; int ind = (n&1 ? n/2 + 1 : n/2); for(int i=1;i<=n/2;++i){ int a = (res[i] - res[l] + mod) % mod; a *= (l == 0 ? 1 : binpow(pi[l],mod-2)); a %= mod; int b = (res[r] - res[r - (i - l)] + mod) % mod; b *= binpow(pi[r - (i - l)],mod-2); b %= mod; // cout << a << ' ' << b << '\n'; if(a == b){ l = i; r = n-l; cnt += 2; } } cout << cnt; } signed main(){ int t; cin >> t; for(int tt=0;tt<t;++tt){ solve(); cout << '\n'; } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |