結果

問題 No.1848 Long Prefixes
ユーザー 👑 potato167
提出日時 2025-04-17 11:05:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,732 bytes
コンパイル時間 2,557 ms
コンパイル使用メモリ 198,924 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-17 11:05:41
合計ジャッジ時間 5,574 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 WA * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;

// Z-algorithm on string s, returns Z array of length n (1-based indexing for runs)
vector<int> Zalgo(const string &s) {
    int n = s.size();
    vector<int> Z(n);
    int l = 0, r = 0;
    Z[0] = n;
    for(int i = 1; i < n; i++) {
        if(i <= r) Z[i] = min(r - i + 1, Z[i - l]);
        while(i + Z[i] < n && s[Z[i]] == s[i + Z[i]]) Z[i]++;
        if(i + Z[i] - 1 > r) {
            l = i;
            r = i + Z[i] - 1;
        }
    }
    return Z;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<ll> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    string S;
    cin >> S;

    // Compute Z on S
    vector<int> Z = Zalgo(S);

    // prefix sums of A for runs (1-based for convenience)
    vector<ll> pref(N+1, 0);
    for(int i = 1; i <= N; i++) {
        pref[i] = pref[i-1] + A[i-1];
    }

    ll ans = 0;
    ll A1 = A[0];

    // Precompute half-sum for triangular terms
    auto tri = [&](ll x){
        x %= MOD;
        return x * ((x + 1) % MOD) % MOD * ((MOD + 1) / 2) % MOD;
    };

    for(int u = 1; u <= N; u++){
        int r = Z[u-1];  // number of matching runs
        if(r <= 0) continue;
        ll Au = A[u-1];

        // sum1: sum over t=1..Au of min(A1, t)
        ll sum1 = 0;
        if(Au <= A1){
            sum1 = tri(Au);
        } else {
            // A1 * (Au - A1) + sum_{t=1..A1} t
            ll part1 = (A1 % MOD) * ((Au - A1) % MOD) % MOD;
            ll part2 = tri(A1);
            sum1 = (part1 + part2) % MOD;
        }
        ans = (ans + sum1) % MOD;

        // if r >= 2, additional
        if(r >= 2){
            // number of t such that full first-run match: t <= Au - A1 + 1
            ll C = Au - A1 + 1;
            if(C <= 0) continue;
            C %= MOD;
            // compute extraLen = sum_{i=2..r-1} A[i] + min(A[r], A[u+r-1])
            // careful: run index u+r-1 <= N?
            if(u + r - 2 >= N) {
                // suffix runs end before completing r runs
                // actually Z gives char matches but run-level may be truncated
                // so effective r_run = number of runs fully inside string
                // But suffix run count is N-u+1; we match at most that many runs
                r = min(r, N - u + 1);
                if(r < 2) continue;
            }
            ll sumRuns = (pref[r-1] - pref[1] + MOD) % MOD;  // sum A[2..r-1]
            ll minLast = min(A[r-1], A[u+r-2]) % MOD;       // A[r], A[u+r-1]
            ll extra = (sumRuns + minLast) % MOD;
            ans = (ans + C * extra) % MOD;
        }
    }

    cout << ans << "\n";
    return 0;
}
0