[AI Readability Summary] This construction problem asks you to transmit an array of length 100 reliably over a channel with a high risk of tampering. The core idea is to treat the original array as the coefficients of a polynomial, evaluate it at 150 points, send each value multiple times, and then recover the original sequence through majority-based point filtering and Lagrange interpolation. The main challenge is avoiding total reconstruction failure caused by severe distortion at individual positions. Keywords: fault-tolerant encoding, polynomial interpolation, Lagrange reconstruction.
The technical specification is straightforward
| Parameter | Value |
|---|---|
| Problem | Luogu P9165 / INOH Round 1 “Accident” |
| Language | C++ |
| Core method | Redundant transmission + polynomial coefficient encoding + Lagrange interpolation |
| Modulus | 998244353 |
| Array length | 100 |
| Transmission limit | 750 |
| Key parameters | S=150, K=5 |
| Core dependencies | vector, map, fast exponentiation over a finite field |
| Source | Organized from a Blog Garden solution note |
This problem is fundamentally about recoverable encoding over a corrupted channel
The total transmission length cannot exceed 750, so you cannot repeat every element indefinitely. If you simply send each value in the original array multiple times, then although you may recover each individual position by taking the mode, the final requirement is that all 100 positions must be correct. That joint success probability collapses very quickly.
The original analysis first examines the most naive strategy: suppose you send S values, and repeat each value K=floor(750/S) times. If tampered values are almost always distinct from one another, then as long as at least 2 correct copies remain, you can identify the true value via majority frequency.
The single-position recovery probability has a direct combinatorial form
For one transmitted value, the probability of successful recovery is:
P(success)=1-(C(K,0)+C(K,1))/2^K=1-(1+K)/2^KThis means failure occurs only in two cases: either there are 0 correct copies, or there is only 1 correct copy.
If you directly transmit the original array, then S=100 and K=7, so the single-position success probability is about 0.9375. However, the overall success probability is about 0.9375^100, which is practically unusable.
A better construction allows any 100 valid values to reconstruct the original array
The key shift is this: you no longer require “position i must recover value i.” Instead, you only need enough valid information from anywhere to reconstruct the full array.
This naturally leads to polynomial recovery. Treat the length-100 array as the coefficients of a degree-99 polynomial. During encoding, evaluate the polynomial at multiple points. During decoding, as long as you obtain at least 100 correct point-value pairs, you can uniquely interpolate the original polynomial and then read back all coefficients.
The difference between two polynomial modeling choices matters
The original solution mentions two approaches:
- Treat the array as point values, which requires frequent interpolation and leads to higher complexity.
- Treat the array as coefficients, which only requires one interpolation step from point values back to coefficients and is easier to implement.
So the final design uses the “array as coefficients” approach.
Choosing S=150 and K=5 gives a better balance between success rate and capacity
The total transmission count is S*K=150*5=750, which exactly reaches the limit. For each sample point, you send the same value 5 times. Then the probability that a point is received correctly at least twice is:
1-(1+5)/2^5=26/32=0.8125The expected number of valid sample points among 150 points is approximately:
150 * 0.8125 = 121.875That means you can expect about 121 valid points on average, which is safely above the minimum 100 points needed to recover a degree-99 polynomial. Therefore, the overall success probability is much better.
The encoding process evaluates the polynomial at x=1 to 150
Let the original array a[0..99] be the coefficient array of the polynomial:
f(x)=a0+a1*x+a2*x^2+...+a99*x^99 mod 998244353Then evaluate it for x=1..150, and send each f(x) value 5 times.
vector
<int> Encode(vector<int> vec){
vector
<int> res;
res.reserve(S * K);
for(int x = 1; x <= S; ++x){
long long y = 0;
for(int i = N - 1; i >= 0; --i){
y = (y * x + vec[i]) % P; // Use Horner's method to evaluate the polynomial
}
for(int i = 0; i < K; ++i){
res.emplace_back((int)y); // Repeat each point value K times
}
}
return res;
}This code encodes the original array into 750 transmittable integers.
The decoding process first filters points by majority, then applies Lagrange interpolation
During decoding, treat every 5 values as 5 transmissions of the same sample point. If some value appears at least twice, regard that point as successfully recovered and record (x, y).
As soon as you collect 100 valid points, you can stop and move to interpolation.
vector
<int> Decode(vector<int> vec){
vector<long long> x, y;
x.reserve(N), y.reserve(N);
for(int i = 1; i <= S; ++i){
map<int,int> mp;
for(int j = K * (i - 1); j < K * i; ++j){
++mp[vec[j]]; // Count occurrences of each received value for this sample point
if(mp[vec[j]] >= 2){
x.emplace_back(i); // Record the x-coordinate
y.emplace_back(vec[j]); // Record the trusted point value
break;
}
}
if((int)x.size() >= N) break; // Interpolate once 100 points are collected
}
vector<long long> res = lagrange(x, y);
return vector
<int>(res.begin(), res.end());
}This code extracts enough correct points from noisy transmission data and reconstructs the original array.
Lagrange interpolation is the recovery core of the entire solution
Because the modulus 998244353 is prime, you can safely perform division in the finite field. In practice, compute modular inverses with fast exponentiation. In the original solution, the lagrange function returns the coefficient array of the polynomial, which directly matches the original input array.
long long ksm(long long x,long long y){
long long res = 1;
while(y){
if(y & 1) res = res * x % P; // Multiply during binary exponentiation
x = x * x % P;
y >>= 1;
}
return res;
}This code computes the powers needed for modular inversion.
The engineering value of this solution is that it upgrades local fault tolerance into global recoverability
Directly repeating array elements is essentially local self-repair on each position. Polynomial encoding instead couples all 100 elements into one global object, so any sufficiently large set of correct samples can contribute to recovery. This idea closely resembles erasure coding and Reed-Solomon-style constructions.
For competitive programmers, the most important takeaway is not the interpolation template itself, but the modeling perspective: when per-position recovery has too low a success rate, switch to full-object reconstruction.
FAQ
Why must a point contain at least 2 correct copies?
Because under a large modulus, incorrect values can be treated as almost always distinct. If some value appears at least twice, it is overwhelmingly likely to be the true value. A value that appears only once cannot be distinguished from random corruption.
Why is treating the array as polynomial coefficients better than treating it as point values?
Because the final goal is to recover the full array. If you directly use the array as coefficients, you only need one interpolation step from point values back to coefficients, which is both simpler and more suitable in practice.
Why choose 150 and 5 instead of 100 and 7?
Although 100×7 gives a higher success rate for each individual position, it requires all 100 positions to succeed. In contrast, 150×5 lets you collect any 100 valid points, so the probability of full reconstruction is significantly better.
AI Visual Insight: This solution reframes the problem from “protect every slot” to “protect enough information to rebuild everything.” That shift is what makes polynomial interpolation a practical fault-tolerant encoding strategy here.
Core takeaway: This article reconstructs the Luogu P9165 “Accident” solution and focuses on how to recover the original array under a high-error transmission model using redundant replication and polynomial interpolation. It covers probability analysis, parameter selection, the encoding/decoding workflow, and practical C++ implementation details. It is especially useful for understanding fault-tolerant encoding, Lagrange interpolation, and construction-heavy competitive programming problems.