結果
問題 | No.2454 Former < Latter |
ユーザー |
![]() |
提出日時 | 2023-09-01 23:01:24 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 282 ms / 2,000 ms |
コード長 | 3,569 bytes |
コンパイル時間 | 5,841 ms |
コンパイル使用メモリ | 171,088 KB |
実行使用メモリ | 8,508 KB |
最終ジャッジ日時 | 2025-01-03 11:03:01 |
合計ジャッジ時間 | 8,596 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long int ll;typedef unsigned long long ull;typedef long double ld;int dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 }, dy[8] = { 0, 1, 0, -1, 1, -1, 1, -1 };const long long mod = 998244353;const ll inf = 1LL << 60;const int INF = 5e8;struct RollingHash {private:using ull = unsigned long long;static const ull _mod = 0x1fffffffffffffff;static ull _base;vector<ull> _hashed, _power;inline ull _mul(ull a, ull b) const{ull au = a >> 31;ull ad = a & ((1UL << 31) - 1);ull bu = b >> 31;ull bd = b & ((1UL << 31) - 1);ull mid = ad * bu + au * bd;ull midu = mid >> 30;ull midd = mid & ((1UL << 30) - 1);ull ans = au * bu * 2 + midu + (midd << 31) + ad * bd;ans = (ans >> 61) + (ans & _mod);if (ans >= _mod)ans -= _mod;return ans;}public:RollingHash(const string& s){ll n = s.size();_hashed.assign(n + 1, 0);_power.assign(n + 1, 0);_power[0] = 1;for (ll i = 0; i < n; i++) {_power[i + 1] = _mul(_power[i], _base);_hashed[i + 1] = _mul(_hashed[i], _base) + s[i];if (_hashed[i + 1] >= _mod)_hashed[i + 1] -= _mod;}}// hashの[l,r)のハッシュ値を返すull get(ll l, ll r) const{ull ret = _hashed[r] + _mod - _mul(_hashed[l], _power[r - l]);if (ret >= _mod)ret -= _mod;return ret;}// ハッシュ値h1と長さh2lenのハッシュ値h2を結合ull connect(ull h1, ull h2, ll h2len) const{ull ret = _mul(h1, _power[h2len]) + h2;if (ret >= _mod)ret -= _mod;return ret;}void connect(const string& s){ll n = _hashed.size() - 1, m = s.size();_hashed.resize(n + m + 1);_power.resize(n + m + 1);for (ll i = n; i < n + m; i++) {_power[i + 1] = _mul(_power[i], _base);_hashed[i + 1] = _mul(_hashed[i], _base) + s[i - n];if (_hashed[i + 1] >= _mod)_hashed[i + 1] -= _mod;}}// hash1の区間[l1,r1)とhash2の区間[l2,r2)のlcp(最長共通接頭辞)の長さを返すll LCP(const RollingHash& b, ll l1, ll r1, ll l2, ll r2) const{ll len = min(r1 - l1, r2 - l2);ll low = -1, high = len + 1;while (high - low > 1) {ll mid = (low + high) / 2;if (get(l1, l1 + mid) == b.get(l2, l2 + mid))low = mid;elsehigh = mid;}return low;}};mt19937_64 mt { (unsigned int)time(NULL) };RollingHash::ull RollingHash::_base = mt() % RollingHash::_mod;void solve(){int n;string s;cin >> n >> s;RollingHash rh(s);int ans = 0;for (int i = 1; i < n; i++) {int l = 0, r = min(i, n - i + 1) + 1;while (r - l > 1) {int mid = (r + l) / 2;auto hash1 = rh.get(0, mid);auto hash2 = rh.get(i, i + mid);if (hash1 == hash2)l = mid;elser = mid;}if (l < i and i + l < n) {ans += (s[l] < s[i + l]);} else if (l == i and i + l == n) {ans += 0;} else if (i + l < n)ans++;}cout << ans << endl;}int main(){int t;cin >> t;while (t--)solve();}