結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
コンテスト
ユーザー りあん
提出日時 2020-11-23 07:52:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 568 ms / 2,000 ms
コード長 2,269 bytes
コンパイル時間 3,637 ms
コンパイル使用メモリ 210,760 KB
最終ジャッジ日時 2025-01-16 04:51:48
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
const int M = 1000000007;
const long long LM = 1LL << 60;


long long solve(const string& s_) {
    string s = "^" + s_;
    int n = s.length();
    vector<vector<long long>> pl(n, vector<long long>(3, 0)), gpl(n, vector<long long>(3, 0));
    pl[0][0] = 1;
    vector<tuple<int, int, int>> g;
    for (int j = 1; j < n; ++j) {
        vector<tuple<int, int, int>> g1, g2;
        for (auto [i, d, k] : g) {
            if (i > 0 && s[i - 1] == s[j]) {
                g1.emplace_back(i - 1, d, k);
            }
        }
        int r = -j;
        for (auto [i, d, k] : g1) {
            if (i - r != d) {
                g2.emplace_back(i, i - r, 1);
                if (k > 1) {
                    g2.emplace_back(i + d, d, k - 1);
                }
            }
            else {
                g2.emplace_back(i, d, k);
            }
            r = i + (k - 1) * d;
        }
        if (j > 1 && s[j - 1] == s[j]) {
            g2.emplace_back(j - 1, j - 1 - r, 1);
            r = j - 1;
        }
        g2.emplace_back(j, j - r, 1);
        g.clear();
        for (auto [i, d, k] : g2) {
            if (g.empty() || get<1>(g[(int)g.size() - 1]) != d) {
                g.emplace_back(i, d, k);
            }
            else {
                get<2>(g[(int)g.size() - 1]) += k;
            }
        }
        for (auto [i, d, k] : g) {
            r = i + (k - 1) * d;
            vector<long long> m = { 0LL, pl[r - 1][0], pl[r - 1][1] };
            if (k > 1) {
                m[1] += gpl[i - d][1];
                m[2] += gpl[i - d][2];
            }
            if (d <= i) {
                gpl[i - d] = m;
            }
            pl[j][1] += m[1];
            pl[j][2] += m[2];
        }
    }

    long long ans = 0;
    vector<long long> a(n);
    a[0] = pl[0][2];
    for (int i = 1; i < n; ++i) {
        a[i] = a[i - 1] + pl[i][2];
    }
    for (auto [i, d, k] : g) {
        for (int j = 0; j < k; ++j) {
            if (i + d * j > 1) {
                ans += a[i + d * j - 2];
            }
        }
    }
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    string s;
    cin >> s;
    cout << solve(s) << '\n';
    return 0;
}
0