o1 爆切 F 题
Correct Approach:
-
Modeling the Problem as a Markov Chain:
- States: Each state represents the current word being spoken (from 1 to ( n )).
- Transitions:
- From state 1:
- Move to state 2 with probability ( \frac{a_1}{a_1 + b_1} ).
- Stay at state 1 with probability ( \frac{b_1}{a_1 + b_1} ).
- From state ( i ) (( 2 \leq i \leq n-1 )):
- Move to state ( i+1 ) with probability ( \frac{a_i^2}{a_i^2 + 2a_i b_i + b_i^2} ).
- Stay at state ( i ) with probability ( \frac{2a_i b_i}{a_i^2 + 2a_i b_i + b_i^2} ).
- Move back to state ( i-1 ) with probability ( \frac{b_i^2}{a_i^2 + 2a_i b_i + b_i^2} ).
- From state ( n ):
- Absorbing state (stop speaking).
- From state 1:
-
Setting Up the System of Linear Equations:
- Let ( E[i] ) denote the expected number of words spoken starting from word ( i ).
- For ( i < n ): [ E[i] = 1 + P(i \rightarrow i-1) \cdot E[i-1] + P(i \rightarrow i) \cdot E[i] + P(i \rightarrow i+1) \cdot E[i+1] ]
- Rearranging: [ (1 - P(i \rightarrow i)) \cdot E[i] - P(i \rightarrow i-1) \cdot E[i-1] - P(i \rightarrow i+1) \cdot E[i+1] = 1 ]
- For ( i = n ): [ E[n] = 1 ]
- This forms a tridiagonal system which can be efficiently solved using the Thomas Algorithm.
-
Implementing the Thomas Algorithm:
- Forward Sweep:
- Modify the coefficients to eliminate the lower diagonal.
- Backward Substitution:
- Solve for the expected values starting from the last equation.
- Forward Sweep:
-
Handling Modular Arithmetic:
- Since the problem requires the answer modulo ( 10^9 + 7 ), we must perform all calculations under this modulus.
- Fractions are handled using modular inverses.
-
Edge Cases:
- If ( n = 1 ), the expected number of words spoken is simply 1.
Final Implementation:
Below is the corrected C++ implementation based on the above reasoning. The key correction involves properly handling the last word by adjusting the condition in the loop that sets up the tridiagonal system.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
// Fast exponentiation to compute x^e mod MOD
ll powmod_func(ll x, ll e, ll mod) {
ll res = 1;
x %= mod;
if(x < 0) x += mod;
while(e > 0){
if(e & 1){
res = res * x % mod;
}
x = x * x % mod;
e >>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
if(n ==1){
cout << "1";
return 0;
}
vector<ll> a(n-1), b(n-1);
for(int i=0;i<n-1;i++) cin >> a[i];
for(int i=0;i<n-1;i++) cin >> b[i];
// Initialize A, B, C, D
// A: lower diagonal, size n-1
// B: main diagonal, size n-1
// C: upper diagonal, size n-1
// D: constants, size n-1
vector<ll> A(n-1,0), B_coeff(n-1,0), C(n-1,0), D(n-1,0);
for(int i=0;i<n-1;i++){
if(i ==0){
// i=0 corresponds to word1
ll a1 = a[i];
ll b1 = b[i];
ll denom = (a1 + b1) % MOD;
ll inv_denom = powmod_func(denom, MOD-2, MOD);
// P_forward = a1 / (a1 + b1)
ll P_forward = a1 * inv_denom % MOD;
// P_stay = b1 / (a1 + b1)
ll P_stay = b1 * inv_denom % MOD;
// Set up equation: (1 - P_stay) * E0 - P_forward * E1 =1
B_coeff[i] = (1 - P_stay + MOD) % MOD; // 1 - P_stay
C[i] = (MOD - P_forward) % MOD; // -P_forward
D[i] =1;
}
else{
ll ai = a[i];
ll bi = b[i];
ll denom = (ai * ai % MOD + 2 * ai % MOD * bi % MOD + bi * bi % MOD) % MOD;
ll inv_denom = powmod_func(denom, MOD-2, MOD);
// P_forward = a_i^2 / denom
ll P_forward = (ai * ai % MOD) * inv_denom % MOD;
// P_stay = 2 * a_i * b_i / denom
ll P_stay = (2 * ai % MOD * bi % MOD) * inv_denom % MOD;
// P_backward = b_i^2 / denom
ll P_backward = (bi * bi % MOD) * inv_denom % MOD;
if(i < n-2){
// Normal variable
A[i] = (MOD - P_backward) % MOD; // -P_backward
B_coeff[i] = (1 - P_stay + MOD) % MOD; // 1 - P_stay
C[i] = (MOD - P_forward) % MOD; // -P_forward
D[i] =1;
}
else{
// Last variable (i = n-2 corresponds to word n-1)
A[i] = (MOD - P_backward) % MOD; // -P_backward
B_coeff[i] = (1 - P_stay + MOD) % MOD; // 1 - P_stay
C[i] =0; // No upper diagonal for the last equation
// D[i] =1 + P_forward * E_n, where E_n =1
D[i] = (1 + P_forward) % MOD;
}
}
}
// Forward sweep
vector<ll> cprime(n-1,0), dprime(n-1,0);
// i=0
ll B0 = B_coeff[0];
ll C0 = C[0];
ll D0 = D[0];
ll invB0 = powmod_func(B0, MOD-2, MOD);
cprime[0] = C0 * invB0 % MOD;
dprime[0] = D0 * invB0 % MOD;
// i=1 to n-2
for(int i=1;i<n-1;i++){
ll Ai = A[i];
ll Bi = B_coeff[i];
ll Ci = C[i];
ll Di = D[i];
// temp = B[i] - A[i] * cprime[i-1}
ll temp = (Bi + MOD - (Ai * cprime[i-1] % MOD)) % MOD;
if(temp ==0){
// No solution, but per problem constraints, it's always solvable
// To avoid division by zero, set E=0 (though it shouldn't happen)
cprime[i] =0;
dprime[i] =0;
continue;
}
ll inv_temp = powmod_func(temp, MOD-2, MOD);
cprime[i] = (Ci * inv_temp) % MOD;
dprime[i] = ((Di + MOD - (Ai * dprime[i-1] % MOD)) % MOD * inv_temp) % MOD;
}
// Back substitution
vector<ll> E(n-1,0);
E[n-2] = dprime[n-2];
for(int i=n-3;i>=0;i--){
E[i] = (dprime[i] + MOD - (cprime[i] * E[i+1] % MOD)) % MOD;
}
// The answer is E[0]
cout << E[0];
}
Explanation of Corrections:
-
Condition Adjustment:
- Original Issue: The original code incorrectly treated the last variable (corresponding to the second last word) as a normal variable.
- Correction: The condition
if(i < n-2)correctly identifies whether the current word is a normal word or the last word. This ensures that the last word's transition probabilities are handled appropriately.
-
Handling the Last Variable:
- For the last variable (word ( n-1 )), there is no ( E[n] ) because ( E[n] = 1 ) is known.
- The equation for the last variable is adjusted to account for this by setting ( C[i] = 0 ) and adjusting ( D[i] ) accordingly.
-
Modular Inverse:
- All divisions are handled using modular inverses to ensure correctness under modulo ( 10^9 + 7 ).
-
Ensuring Non-Zero Denominators:
- The code includes a check to avoid division by zero, though according to problem constraints, the system should always be solvable.
Validation with Sample Input:
Let's validate the corrected code with the provided sample:
Input:
3
1 1
1 1
Expected Output:
9
Explanation:
- Word 1:
- ( P(1 \rightarrow 2) = \frac{1}{2} )
- ( P(1 \rightarrow 1) = \frac{1}{2} )
- Word 2:
- ( P(2 \rightarrow 3) = \frac{1}{4} )
- ( P(2 \rightarrow 2) = \frac{1}{2} )
- ( P(2 \rightarrow 1) = \frac{1}{4} )
- Word 3:
- Absorbing state, ( E[3] = 1 )
Solving the system: [ \begin{cases} 0.5 E_1 - 0.5 E_2 = 1 \ -0.25 E_1 + 0.5 E_2 = 1.25 \end{cases} ] Solving these equations yields ( E_1 = 9 ) and ( E_2 = 7 ), which matches the expected output.
Conclusion:
The corrected code now accurately sets up and solves the tridiagonal system representing the Markov chain of Zaoly's speech. By properly handling the last variable and ensuring the correct conditions in the loop, the code now produces the expected results, including for the provided sample input.
