結果

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

ソースコード

diff # 

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

// Z-algorithm
vector<int> Zalgo(const string &s) {
    int n = s.size();
    vector<int> Z(n);
    Z[0] = n;
    int l = 0, r = 0;
    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;
}

ll modmul(ll a, ll b){
    return (a % MOD) * (b % MOD) % MOD;
}

ll modadd(ll a, ll b){
    a += b;
    if(a >= MOD) a -= MOD;
    return a;
}

// triangular sum 1+2+...+x mod MOD
ll tri(ll x){
    x %= MOD;
    return x * ((x + 1) % MOD) % MOD * ((MOD + 1) / 2) % MOD;
}

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

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

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

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

    ll ans = 0;
    ll A1 = A[1] % MOD;

    for(int u = 1; u <= N; u++){
        int r = Z[u-1];  // number of matching characters => matching runs
        // compute Sum1 for run u: sum_{t=1..A[u]} min(A1, A[u]-t+1)
        ll L = A[u];
        ll sum1;
        if(L <= A1){
            sum1 = tri(L);
        } else {
            // = A1*(L-A1) + tri(A1)
            ll part1 = modmul(A1, (L - A1) % MOD);
            ll part2 = tri(A1);
            sum1 = modadd(part1, part2);
        }
        ans = (ans + sum1) % MOD;

        if(r >= 2){
            // ensure suffix has at least r runs: i.e. u+r-1 <= N
            if(u + r - 1 > N) r = N - u + 1;
            if(r >= 2){
                // C_u = sum_{j=2..r-1} A[j] + min(A[r], A[u+r-1])
                ll sum_mid = (pref[r-1] - pref[1]) % MOD;
                if(sum_mid < 0) sum_mid += MOD;
                ll mn = min(A[r], A[u+r-1]) % MOD;
                ll Cu = (sum_mid + mn) % MOD;
                ans = (ans + modmul((A[u] % MOD), Cu)) % MOD;
            }
        }
    }

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