logoChat01.ai

G. The Maximum Prefix time limit per test1 second...

Creado el: 29 de abril de 2025

Respondido usando O4 Mini High por Chat01

Pregunta

G. The Maximum Prefix
time limit per test1 second
memory limit per test256 megabytes
You're going to generate an array a
with a length of at most n
, where each ai
equals either 1
or −1
.

You generate this array in the following way.

First, you choose some integer k
(1≤k≤n
), which decides the length of a
.
Then, for each i
(1≤i≤k
), you set ai=1
with probability pi
, otherwise set ai=−1
(with probability 1−pi
).
After the array is generated, you calculate si=a1+a2+a3+…+ai
. Specially, s0=0
. Then you let S
equal to maxi=0ksi
. That is, S
is the maximum prefix sum of the array a
.

You are given n+1
integers h0,h1,…,hn
. The score of an array a
with maximum prefix sum S
is hS
. Now, for each k
, you want to know the expected score for an array of length k
modulo 109+7
.

Input
Each test contains multiple test cases. The first line contains a single integer t
(1≤t≤5000
) — the number of test cases. Their description follows.

The first line contains an integer n
(1≤n≤5000
).

Then for the following n
lines, each line contains two integers xi
and yi
(0≤xi<109+7
, 1≤yi<109+7
, xi≤yi
), indicating pi=xiyi
.

The next line contains n+1
integers h0,h1,…,hn
(0≤hi<109+7
).

It is guaranteed that the sum of n
over all test cases does not exceed 5000
.

Output
For each test case, output n
integers in one single line, the i
-th of which denotes the expected score for an array of length i
, modulo 109+7
.

Formally, let M=109+7
. It can be shown that the answer can be expressed as an irreducible fraction pq
, where p
and q
are integers and q≢0(modM)
. Output the integer equal to p⋅q−1modM
. In other words, output such an integer x
that 0≤x<M
and x⋅q≡p(modM)
.

Example
Input
4
2
1 2
1 2
1 2 3
3
1 3
1 4
5 5
1 1 1 1
3
2 5
4 6
0 2
4 3 2 1
5
5 6
5 7
1 6
1 3
4 7
9 0 4 5 2 4

output
500000005 750000007
1 1 1
200000005 333333339 333333339
500000005 880952391 801587311 781746041 789304620

Note
In the first test case, if we choose k=1
, there are 2
possible arrays with equal probabilities: [1]
and [−1]
. The S
values for them are 1
and 0
. So the expected score is 12h0+12h1=32
. If we choose k=2
, there are 4
possible arrays with equal probabilities: [1,1]
, [1,−1]
, [−1,1]
, [−1,−1]
, and the S
values for them are 2,1,0,0
. So the expected score is 12h0+14h1+14h2=74
.

In the second test case, no matter what the S
value is, the score is always 1
, so the expected score is always 1
.

Pensamiento

Considering backward dynamic programming

They suggest a different approach — starting the dynamic programming process from the end and working backwards, rather than moving forward. The idea is to compute the probability for every step, updating it as we go. The key is treating the next possible state as the remaining maximum prefix sum, which helps manage the suffix sum. By looking at it this way, it becomes analogous to the original approach, but applied in reverse. It seems like this could simplify things a bit!

Reversing DP process

The idea is that f[i][j] represents the probability that the suffix a[i..a_n] has a maximum prefix sum equal to j. In reverse dynamic programming (DP), we calculate the probability for each start position i and each current maximum sum j. By generating an array with random probabilities, we work out f[1][j] for the full length, but we need this for smaller lengths too. They then compute contributions for different lengths, adjusting coefficients using reverse DP to get the expected score for each k.

Processing contributions for DP

The idea here is calculating the contributions from each state, which is represented as g[t][s]. This corresponds to how much state f[t][s] contributes to the final answer. The goal is to calculate contributions for all prefixes of a given length, using reverse DP. This means we start computing from the initial state and determine the coefficients that contribute to the full sum, adjusting accordingly for different prefix lengths. The result will give the expected scores for each prefix as we work through the process.

Documenting Dynamic Programming Solution

I'm crafting a detailed explanation for a dynamic programming problem about calculating prefix sums for expected values using probabilities. It uses a "reverse contribution" approach to avoid the inefficiencies of a direct O(n^3) solution, making it feasible for large test sizes with an O(n^2) complexity. I'll also prepare the C++ code solution, breaking it down with comments to explain key steps clearly. Since the user didn't specify asking for it, let's stick to this programming solution with an explanation for context. I'll present the final answer in markdown code format.

Thought for 1m 39s

Respuesta

To solve this in O(n2)O(n^2), we use a “reverse-DP on contributions” trick. First, observe that if you ran the straightforward DP for the full length nn

f[n+1][0]=1,f[n+1][j]=0 (j>0),f[i][j]=pi f[i+1][ j+1 ]+(1−pi) f[i+1,max⁡(j−1,0)],\begin{aligned} f[n+1][0]&=1,\quad f[n+1][j]=0\ (j>0),\\ f[i][j]&=p_i\,f[i+1][\,j+1\,]+(1-p_i)\,f\bigl[i+1,\max(j-1,0)\bigr], \end{aligned}

then the expected score for length nn would be

∑j=0nhj f[1][j].\sum_{j=0}^n h_j\,f[1][j].

But the same linear recurrence applies if you stop at any earlier position k+1k+1 (i.e.\ take f[k+1][0]=1f[k+1][0]=1 as your “initial” condition). By linearity, the answer for length kk is exactly the coefficient with which that “f[k+1][0]f[k+1][0]” appears in the full-length sum. If you call that coefficient g[k+1][0]g[k+1][0], you get the following very simple O(n2)O(n^2) DP on gg:

  1. Initialize g[1][j]=hj(0≤j≤n).g[1][j] = h_j\quad(0\le j\le n).
  2. For i=1i=1 to nn, for each 0≤j≤n0\le j\le n: g[i+1][j]=pi   g[i][j+1]  +  (1−pi)  g[i,max⁡(j−1,0)](mod109+7).g[i+1][j] = p_i\;\,g[i][j+1] \;+\;(1-p_i)\;g\bigl[i,\max(j-1,0)\bigr] \pmod{10^9+7}.
  3. Then for each k=1…nk=1\ldots n, answer[k]  =  g[k+1][0]. \text{answer}[k] \;=\; g[k+1][0].

Below is a concise C++ implementation:

cpp
#include <bits/stdc++.h>
using namespace std;
static const int MOD = 1000000007;

// Fast exponentiation to compute a^(MOD-2) % MOD
long long modexp(long long a, long long b = MOD-2) {
    long long r = 1 % MOD;
    while (b > 0) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

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

    int t; 
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        vector<long long> p(n+1), q(n+1);
        for (int i = 1; i <= n; i++) {
            long long x, y;
            cin >> x >> y;
            // p_i = x * inv(y) % MOD
            p[i] = x * modexp(y) % MOD;
            // q_i = 1 - p_i (mod MOD)
            q[i] = (1 - p[i] + MOD) % MOD;
        }

        // Read the h[0..n] array
        vector<long long> h(n+1);
        for (int i = 0; i <= n; i++) {
            cin >> h[i];
        }

        // We'll keep two rolling rows of g[*][*]:
        vector<long long> cur(n+2), nxt(n+2);
        // Base: g[1][j] = h[j]
        for (int j = 0; j <= n; j++) {
            cur[j] = h[j];
        }

        vector<long long> ans(n+1);
        // Build g row by row
        for (int i = 1; i <= n; i++) {
            // Compute g[i+1][j] = p_i*cur[j+1] + q_i*cur[max(j-1,0)]
            for (int j = 0; j <= n; j++) {
                long long t1 = (j+1 <= n ? cur[j+1] : 0);
                long long t2 = (j > 0 ? cur[j-1] : cur[0]);
                nxt[j] = (p[i] * t1 + q[i] * t2) % MOD;
            }
            ans[i] = nxt[0];       // answer for length i
            swap(cur, nxt);
        }

        // Output
        for (int i = 1; i <= n; i++) {
            cout << ans[i] << (i==n? '\n':' ');
        }
    }
    return 0;
}

Complexity.

  • Each test runs an O(n2)O(n^2) DP (the double loop on i=1..ni=1..n, j=0..nj=0..n), and the sum of all nn over all tests is at most 5000, so this easily fits in 1 second.
  • Memory is O(n)O(n) extra for the rolling arrays.

Compartir este Q&A