// QCFium 法 #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #ifndef HIDDEN_IN_VS // 折りたたみ用 // 警告の抑制 #define _CRT_SECURE_NO_WARNINGS // ライブラリの読み込み #include using namespace std; // 型名の短縮 using ll = long long; using ull = unsigned long long; // -2^63 ~ 2^63 = 9 * 10^18(int は -2^31 ~ 2^31 = 2 * 10^9) using pii = pair; using pll = pair; using pil = pair; using pli = pair; using vi = vector; using vvi = vector; using vvvi = vector; using vvvvi = vector; using vl = vector; using vvl = vector; using vvvl = vector; using vvvvl = vector; using vb = vector; using vvb = vector; using vvvb = vector; using vc = vector; using vvc = vector; using vvvc = vector; using vd = vector; using vvd = vector; using vvvd = vector; template using priority_queue_rev = priority_queue, greater>; using Graph = vvi; // 定数の定義 const double PI = acos(-1); int DX[4] = {1, 0, -1, 0}; // 4 近傍(下,右,上,左) int DY[4] = {0, 1, 0, -1}; int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF; // 入出力高速化 struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp; // 汎用マクロの定義 #define all(a) (a).begin(), (a).end() #define sz(x) ((int)(x).size()) #define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x)) #define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x)) #define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");} #define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順 #define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順 #define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順 #define repe(v, a) for(const auto& v : (a)) // a の全要素(変更不可能) #define repea(v, a) for(auto& v : (a)) // a の全要素(変更可能) #define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索(昇順) #define repis(i, set) for(int i = lsb(set), bset##i = set; i >= 0; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素(昇順) #define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て(昇順) #define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去 #define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了 #define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定 // 汎用関数の定義 template inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; } template inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新(更新されたら true を返す) template inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新(更新されたら true を返す) template inline T getb(T set, int i) { return (set >> i) & T(1); } template inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod // 演算子オーバーロード template inline istream& operator>>(istream& is, pair& p) { is >> p.first >> p.second; return is; } template inline istream& operator>>(istream& is, vector& v) { repea(x, v) is >> x; return is; } template inline vector& operator--(vector& v) { repea(x, v) --x; return v; } template inline vector& operator++(vector& v) { repea(x, v) ++x; return v; } #endif // 折りたたみ用 #if __has_include() #include using namespace atcoder; #ifdef _MSC_VER #include "localACL.hpp" #endif //using mint = modint1000000007; using mint = modint998244353; //using mint = modint; // mint::set_mod(m); namespace atcoder { inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; } inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; } } using vm = vector; using vvm = vector; using vvvm = vector; using vvvvm = vector; using pim = pair; #endif #ifdef _MSC_VER // 手元環境(Visual Studio) #include "local.hpp" #else // 提出用(gcc) inline int popcount(int n) { return __builtin_popcount(n); } inline int popcount(ll n) { return __builtin_popcountll(n); } inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : -1; } inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; } template inline int lsb(const bitset& b) { return b._Find_first(); } inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; } inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; } #define dump(...) #define dumpel(v) #define dump_list(v) #define dump_mat(v) #define input_from_file(f) #define output_to_file(f) #define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す #endif // 0:30 挑戦開始 //【最長増加部分列】O(n log n) /* * 数列 a[0..n) の(狭義)最長増加部分列の長さを返す. * *(二分探索で高速化したインライン DP) */ template int LIS_length_to_val(const vector& a) { // verify : https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_x int n = sz(a); // dp_i[j] : a[0..i) で,長さが j である増加部分列の右端の値の最小値 // 短い増加部分列はそれより長い増加部分列の部分列なので,広義単調増加性がある. vector dp(n + 1, T(INFL)); dp[0] = -T(INFL); //(例)a[0..5) = [4, 2, 3, 3, 1] のとき // dp_0[0..5] = [-INF, INF, INF, INF, INF, INF] // dp_1[0..5] = [-INF, 4, INF, INF, INF, INF] // dp_2[0..5] = [-INF, 2, INF, INF, INF, INF] // dp_3[0..5] = [-INF, 2, 3, INF, INF, INF] // dp_4[0..5] = [-INF, 2, 3, INF, INF, INF] // dp_5[0..5] = [-INF, 1, 3, INF, INF, INF] rep(i, n) { // 右端が a[i] 以上であるような増加部分列の最小長さ j を得る. int j = lbpos(dp, a[i]); // 長さ j の増加部分列の右端を a[i] に置き換える. dp[j] = a[i]; // これより短いものは右端を a[i] に置き換えても得しないので無視できる. // これより長いものはそもそも右端を a[i] に置き換えることができない. } // 右端の値が設定できている長さの最大値を求める. int res = 0; repir(j, n, 1) { if (dp[j] != T(INFL)) { res = j; break; } } return res; } // 0:43 何も分からんし愚直を書いてみる. mint naive(int n, string s) { vi p(n); iota(all(p), 1); mint res = 0; repp(p) { bool ok = true; rep(i, n - 1) { if ((s[i] == '<') != (p[i] < p[i + 1])) { ok = false; break; } } if (!ok) continue; if (LIS_length_to_val(p) != 2) continue; dump(p); res++; } return res; } //【階乗など(法が大きな素数)】 /* * Factorial_mint(int N) : O(n) * N まで計算可能として初期化する. * * mint fact(int n) : O(1) * n! を返す. * * mint fact_inv(int n) : O(1) * 1/n! を返す(n が負なら 0 を返す) * * mint inv(int n) : O(1) * 1/n を返す. * * mint perm(int n, int r) : O(1) * 順列の数 nPr を返す. * * mint bin(int n, int r) : O(1) * 二項係数 nCr を返す. * * mint bin_inv(int n, int r) : O(1) * 二項係数の逆数 1/nCr を返す. * * mint mul(vi rs) : O(|rs|) * 多項係数 nC[rs] を返す.(n = Σrs) * * mint hom(int n, int r) : O(1) * 重複組合せの数 nHr = n+r-1Cr を返す(0H0 = 1 とする) * * mint neg_bin(int n, int r) : O(1) * 負の二項係数 nCr = (-1)^r -n+r-1Cr を返す(n ≦ 0, r ≧ 0) */ class Factorial_mint { int n_max; // 階乗と階乗の逆数の値を保持するテーブル vm fac, fac_inv; public: // n! までの階乗とその逆数を前計算しておく.O(n) Factorial_mint(int n) : n_max(n), fac(n + 1), fac_inv(n + 1) { // verify : https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b fac[0] = 1; repi(i, 1, n) fac[i] = fac[i - 1] * i; fac_inv[n] = fac[n].inv(); repir(i, n - 1, 0) fac_inv[i] = fac_inv[i + 1] * (i + 1); } Factorial_mint() : n_max(0) {} // ダミー // n! を返す. mint fact(int n) const { // verify : https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b Assert(0 <= n && n <= n_max); return fac[n]; } // 1/n! を返す(n が負なら 0 を返す) mint fact_inv(int n) const { // verify : https://atcoder.jp/contests/abc289/tasks/abc289_h Assert(n <= n_max); if (n < 0) return 0; return fac_inv[n]; } // 1/n を返す. mint inv(int n) const { // verify : https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d Assert(0 < n && n <= n_max); return fac[n - 1] * fac_inv[n]; } // 順列の数 nPr を返す. mint perm(int n, int r) const { // verify : https://atcoder.jp/contests/abc172/tasks/abc172_e Assert(n <= n_max); if (r < 0 || n - r < 0) return 0; return fac[n] * fac_inv[n - r]; } // 二項係数 nCr を返す. mint bin(int n, int r) const { // verify : https://judge.yosupo.jp/problem/binomial_coefficient_prime_mod Assert(n <= n_max); if (r < 0 || n - r < 0) return 0; return fac[n] * fac_inv[r] * fac_inv[n - r]; } // 二項係数の逆数 1/nCr を返す. mint bin_inv(int n, int r) const { // verify : https://www.codechef.com/problems/RANDCOLORING Assert(n <= n_max); Assert(r >= 0 || n - r >= 0); return fac_inv[n] * fac[r] * fac[n - r]; } // 多項係数 nC[rs] を返す. mint mul(const vi& rs) const { // verify : https://yukicoder.me/problems/no/2141 if (*min_element(all(rs)) < 0) return 0; int n = accumulate(all(rs), 0); Assert(n <= n_max); mint res = fac[n]; repe(r, rs) res *= fac_inv[r]; return res; } // 重複組合せの数 nHr = n+r-1Cr を返す(0H0 = 1 とする) mint hom(int n, int r) { // verify : https://mojacoder.app/users/riantkb/problems/toj_ex_2 if (n == 0) return (int)(r == 0); Assert(n + r - 1 <= n_max); if (r < 0 || n - 1 < 0) return 0; return fac[n + r - 1] * fac_inv[r] * fac_inv[n - 1]; } // 負の二項係数 nCr を返す(n ≦ 0, r ≧ 0) mint neg_bin(int n, int r) { // verify : https://atcoder.jp/contests/abc345/tasks/abc345_g if (n == 0) return (int)(r == 0); Assert(-n + r - 1 <= n_max); if (r < 0 || -n - 1 < 0) return 0; return (r & 1 ? -1 : 1) * fac[-n + r - 1] * fac_inv[r] * fac_inv[-n - 1]; } }; // 1:43 // RS対応で順列と対応するタブローの形を決め打ちすればいいのでは?というアイデアに辿り着く. // 2:04 // 組 (P, Q) のうちの P 側はフック長公式で数え上げられる.Q はそれと独立なので半分解けた! mint WA(int n, string s) { rep(i, n) if (s[i] == '<' && s[i + 1] == '<') return 0; Factorial_mint fm(n); mint res = 0; int h2_min = 0; repe(c, s) h2_min += c == '<'; if (h2_min == 0) return 0; repi(h2, h2_min, n / 2) { int h1 = n - h2; mint P = fm.fact(n); P *= fm.fact_inv(h2); P *= fm.fact_inv(h1 + 1); P *= h1 - h2 + 1; mint Q = 1; // 嘘.タブローの形によって 0 個だったり複数存在したりもする. res += P * Q; dump(h2, P, Q, P * Q); } return res; } //【1 の連の長さ】O(n) /* * ビット列 s[0..n) について,'0' で区切られた '1' の連の長さを順に並べた列を返す. */ vi length1(const string& s, char one = '1') { // verify : https://atcoder.jp/contests/agc046/tasks/agc046_c vi len; int l = 0; repe(c, s) { if (c == one) { l++; } else { len.push_back(l); l = 0; } } len.push_back(l); return len; } // 2:23 // Q の方は 1 列目と 2 列目の長さの差を状態にもつ DP で数え上げられる.ただし O(N^3) mint TLE(int n, string s) { rep(i, n) if (s[i] == '<' && s[i + 1] == '<') return 0; auto lens = length1(s, '>'); ++lens; int K = sz(lens); dump("lens:", lens); // dp_i[j] : lens[0..i) で差が j vm dp(lens[0] + 1); dp.back() = 1; dump("dp:"); dump(dp); repi(k, 1, K - 2) { vm ndp(sz(dp) + lens[k]); rep(j, sz(dp)) { // hj : j 列目に何個使うか repi(h2, 1, min(lens[k] - 1, j)) { int h1 = lens[k] - h2; ndp[j + h1 - h2] += dp[j]; } } dp = move(ndp); dump(dp); } { int k = K - 1; vm ndp(sz(dp) + lens[k]); rep(j, sz(dp)) { // hj : j 列目に何個使うか repi(h2, 1, min(lens[k], j)) { int h1 = lens[k] - h2; ndp[j + h1 - h2] += dp[j]; } } dp = move(ndp); dump(dp); } dp.resize(n + 1); Factorial_mint fm(n); mint res = 0; int h2_min = K - 1; if (h2_min == 0) return 0; dump("h2, P, Q, PQ:"); repi(h2, h2_min, n / 2) { int h1 = n - h2; mint P = fm.fact(n); P *= fm.fact_inv(h2); P *= fm.fact_inv(h1 + 1); P *= h1 - h2 + 1; mint Q = dp[h1 - h2]; res += P * Q; dump(h2, P, Q, P * Q); } return res; } //【間引きいもす法】 /* * Thinning_imos(int n, int m) : O(n + m) * 法を m とし,a[0..n) = 0 で初期化する. * * add(int l, int r, int k, T val) : O(1) * S = {i∈[l..r) | i=k (mod m)} とし a[S] += val とする準備を行う. * * void execute() : O(n) * 実際の加算を行う. * * T [](int i) : O(1) * a[i] を返す. * 制約 : 先に execute() を呼び出すこと. */ template class Thinning_imos { int n, m; vector v; bool ex = false; public: // 法を m とし,a[0..n) = 0 で初期化する. Thinning_imos(int n, int m) : n(n), m(m), v(n + m) { // verify : https://yukicoder.me/problems/no/2359 } Thinning_imos() : n(0), m(1) {} // アクセス inline T const& operator[](int i) const { return v[i]; } inline T& operator[](int i) { return v[i]; } // S = {i∈[l..r) | i=k (mod m)} とし a[S] += val とする準備を行う. void add(int l, int r, int k, T val) { // verify : https://yukicoder.me/problems/no/2359 chmax(l, 0); chmin(r, n); if (l >= r) return; r += smod(k - r, m); l += smod(k - l, m); v[l] += val; v[r] -= val; } // 実際の加算を行う. void execute() { // verify : https://yukicoder.me/problems/no/2359 rep(i, n) v[i + m] += v[i]; ex = true; } #ifdef _MSC_VER friend ostream& operator<<(ostream& os, Thinning_imos a) { if (!a.ex) a.execute(); rep(i, a.n) os << a[i] << " "; return os; } #endif }; // 2:45 // TLE() はいもす法で高速化できる.ただしそれでも O(N^2) mint TLE2(int n, string s) { // RE も吐くっぽい rep(i, n) if (s[i] == '<' && s[i + 1] == '<') return 0; auto lens = length1(s, '>'); ++lens; int K = sz(lens); dump("lens:", lens); // dp_i[j] : lens[0..i) で差が j vm dp(lens[0] + 1); dp.back() = 1; dump("dp:"); dump(dp); repi(k, 1, K - 2) { dump("- - -", k, "- - -"); int N = sz(dp); int nN = N + lens[k]; Thinning_imos imos(nN, 2); rep(j, N) { imos.add(j + lens[k] - 2 * min(lens[k] - 1, j), j + lens[k] - 2 + 1, j + lens[k], dp[j]); } imos.execute(); dp.resize(nN); rep(i, nN) dp[i] = imos[i]; while (!dp.empty() && dp.back() == 0) dp.pop_back(); if (dp.empty()) return 0; dump(dp); } { int k = K - 1; dump("- - -", k, "- - -"); int N = sz(dp); int nN = N + lens[k]; Thinning_imos imos(nN, 2); rep(j, N) { imos.add(j + lens[k] - 2 * min(lens[k], j), j + lens[k] - 2 + 1, j + lens[k], dp[j]); } imos.execute(); dp.resize(n + 1); rep(i, nN) dp[i] = imos[i]; dump(dp); } Factorial_mint fm(n); mint res = 0; int h2_min = K - 1; if (h2_min == 0) return 0; dump("h2, P, Q, PQ:"); repi(h2, h2_min, n / 2) { int h1 = n - h2; mint P = fm.fact(n); P *= fm.fact_inv(h2); P *= fm.fact_inv(h1 + 1); P *= h1 - h2 + 1; mint Q = dp[h1 - h2]; res += P * Q; dump(h2, P, Q, P * Q); } return res; } // 3:13 // ぼんやりと分割統治積が想定な気がするが,必死に定数倍高速化すればワンチャンあるのでは?と思ったので挑戦する. constexpr int LIM = (int)1e5 + 10; int lens[LIM]; int K = 0; mint dp[LIM]; int N = 0; mint imos[LIM]; mint USO(int n, const string& s) { rep(i, n) if (s[i] == '<' && s[i + 1] == '<') return 0; { K = 0; int l = 0; repe(c, s) { if (c == '>') { l++; } else { lens[K++] = l + 1; l = 0; } } lens[K++] = l + 1; } // rep(k, K) cerr << lens[k] << " "; cerr << endl; // dp_i[j] : lens[0..i) で差が j rep(i, lens[0]) dp[i] = 0; dp[lens[0]] = 1; N = lens[0] + 1; int par = lens[0] & 1; rep(i, N) cout << (int)((i & 1) == par) * dp[i] << " "; cout << endl; repi(k, 1, K - 2) { dump("- - -", k, "- - -"); int nN = N + lens[k]; int npar = ~nN & 1; for (int i = npar; i < nN + 2; i += 2) imos[i] = 0; for (int j = par; j < N; j += 2) { int l = j + lens[k] - 2 * min(lens[k] - 1, j); int r = j + lens[k]; imos[l] += dp[j]; imos[r] -= dp[j]; } for (int i = npar; i < nN; i += 2) { dp[i] = imos[i]; imos[i + 2] += imos[i]; } while (nN > 0 && dp[nN - 1] == 0) nN -= 2; if (nN <= 0) return 0; N = nN; par = npar; rep(i, N) cout << (int)((i & 1) == par) * dp[i] << " "; cout << endl; } { int k = K - 1; dump("- - -", k, "- - -"); int nN = N + lens[k]; int npar = ~nN & 1; for (int i = npar; i < nN + 2; i += 2) imos[i] = 0; for (int j = par; j < N; j += 2) { int l = j + lens[k] - 2 * min(lens[k], j); int r = j + lens[k]; imos[l] += dp[j]; imos[r] -= dp[j]; } for (int i = npar; i < nN; i += 2) { dp[i] = imos[i]; imos[i + 2] += imos[i]; } par = npar; rep(i, N) cout << (int)((i & 1) == par) * dp[i] << " "; cout << endl; } // ここから先は速いはずなのでそのままでいい. Factorial_mint fm(n); mint res = 0; int h2_min = K - 1; if (h2_min == 0) return 0; dump("h2, P, Q, PQ:"); repi(h2, h2_min, n / 2) { int h1 = n - h2; mint P = fm.fact(n); P *= fm.fact_inv(h2); P *= fm.fact_inv(h1 + 1); P *= h1 - h2 + 1; mint Q = dp[h1 - h2]; res += P * Q; dump(h2, P, Q, P * Q); } return res; } // 14:41 /* DP テーブルを出力させてみると 0 0 0 1 - - - 1 - - - 0 0 1 0 1 - - - 2 - - - 0 1 0 2 0 1 - - - 3 - - - 0 0 3 0 3 0 1 - - - 4 - - - 0 3 0 6 0 4 0 1 - - - 5 - - - 0 0 9 0 10 0 5 0 1 - - - 6 - - - 0 9 0 19 0 15 0 6 0 1 - - - 7 - - - 0 0 28 0 34 0 21 0 7 0 1 - - - 8 - - - 0 28 0 62 0 55 0 28 0 8 0 1 - - - 9 - - - 0 0 90 0 117 0 83 0 36 0 9 0 1 - - - 10 - - - 0 90 0 117 0 83 0 36 0 9 0 1 0 となった.どうみても二項係数だが,端っこが切り詰められている. これは通行禁止線がある場合の経路数の数え上げなので,反射原理で計算できる. この例だと, 0 = bin(9,6) - bin(9,3) 90 = bin(9,5) - bin(9,2) 117 = bin(9,4) - bin(9,1) 83 = bin(9,3) - bin(9,0) のようになっている. */ //【畳込み(複数,mod 998244353)】O(n (log n)^2) /* * 数列の集合 a の要素を全て畳込んだ結果(長さは n)を返す. */ vm multi_convoluion(vvm a) { // verify : https://judge.yosupo.jp/problem/product_of_polynomial_sequence int m = sz(a); if (m == 0) return vm{ 1 }; // (要素数, 数列の番号) の組を要素数昇順に記録する. priority_queue_rev q; rep(i, m) { if (a[i].empty()) return vm(); q.push({ sz(a[i]), i }); } // 積のコストが小さい順に掛けていく(マージテク) while (sz(q) >= 2) { auto [ni, i] = q.top(); q.pop(); auto [nj, j] = q.top(); q.pop(); a[i] = convolution(a[i], a[j]); q.push({ ni + nj - 1, i }); } return a[q.top().second]; } // 15:05 // O(N^2) の DP を分割統治積+反射原理に置き換えて O(N (log N)^2) にした. mint solve(int n, string s) { rep(i, n) if (s[i] == '<' && s[i + 1] == '<') return 0; auto lens = length1(s, '>'); ++lens; int K = sz(lens); dump("lens:", lens); vvm fs; repi(k, 1, K - 2) { vm f(lens[k] - 1, 1); fs.push_back(f); } { int k = K - 1; vm f(lens[k], 1); fs.push_back(f); } auto f = multi_convoluion(fs); dump(f); Factorial_mint fm(n); mint res = 0; int h2_min = K - 1; if (h2_min == 0) return 0; dump("h2, P, Q, PQ:"); int lp = -lens[0], rp = sz(f) - 1; repi(h2, h2_min, n / 2) { int h1 = n - h2; mint P = fm.fact(n); P *= fm.fact_inv(h2); P *= fm.fact_inv(h1 + 1); P *= h1 - h2 + 1; dump(rp, lp, (0 <= rp ? f[rp] : 0) - (0 <= lp && lp < sz(f) ? f[lp] : 0)); mint Q = (0 <= rp ? f[rp] : 0) - (0 <= lp && lp < sz(f) ? f[lp] : 0); res += P * Q; lp++; rp--; dump(h2, P, Q, P * Q); } return res; } void bug_find() { #ifdef _MSC_VER // 合わない入力例を見つける. mute_dump = true; mt19937_64 mt; mt.seed((int)time(NULL)); uniform_int_distribution rnd(0LL, 1LL << 60); rep(hoge, 1000) { int n = rnd(mt) % 100 + 2; string s; rep(i, n - 1) s += "<>"[rnd(mt) % 2]; // cout << n << " " << s << endl; auto res_naive = TLE(n, s); // cout << "!" << endl; auto res_solve = solve(n, s); if (res_naive != res_solve) { cout << "----------error!----------" << endl; cout << "input:" << endl; cout << n << endl; cout << s << endl; cout << "results:" << endl; cout << res_naive << endl; cout << res_solve << endl; cout << "--------------------------" << endl; } } mute_dump = false; exit(0); #endif } int main() { input_from_file("input.txt"); // output_to_file("output.txt"); bug_find(); int n; string s; cin >> n >> s; dump(n); dump(s); dump("----"); dump(TLE(n, s)); dump("----"); // 3:04 // まだ O(N^2) だけどとりあえず提出. // cout << TLE2(n, s) << endl; // 3:28 // ちょっと定数倍高速化してみた.相変わらず O(N^2) だけど提出. // 3:50 // dp[] の密度が 1/2 なので 2 倍高速化できた.→定数倍高速化バトルに勝利! // 13:06 // インクリメント量を 2 にしたつもりが 1 のままだったので再提出. // なんでこれで AC してたんだ・・・? → 2,213 ms / 4,000 ms で AC // 15:06 // O(N^2) の DP を分割統治積+反射原理に置き換えて O(N (log N)^2) にした. cout << solve(n, s) << endl; }