洛谷-P9165 「INOH」Round 1 - 意外 题解

Solution

由题意得，传输的数组长度必须 \(\le 750\)。

最朴素的容错方式是增加冗余。假设需要传递 \(S\) 个数值，每个数值重复传输 \(K=\left\lfloor\frac{750}{S}\right\rfloor\) 份。由于模数大，篡改后的数可以认为各不相同。所以在 \(K\) 份中只要正确的数字保留了 \(\ge 2\) 份，就能通过取众数还原，否则该数值丢失。因此单个数成功概率为：

最直接的想法是直接传原数组，每个数传 \(7\) 份。这样单个数成功概率为 \(0.9375\)，但是需要 \(100\) 个数全部成功才行，总成功率为 \(0.9375^{100}\approx0\)，没有前途。

能否找到一种方法，使得只需要任意 \(100\) 个有效数值就能反推原数组？不妨考虑多项式表示法。

有两种构造多项式的方法：

1. 数组作为点值：解码器需要做 \(N\) 次 \(O(N^2)\) 插值，总时间复杂度 \(O(N^3)\)。
2. 数组作为系数：拉格朗日插值提供了 \(O(N^2)\) 的点值转系数算法。

综上，我们采用方法 2。

取 \(S=150\)，\(K=5\)，期望接收到 \(\approx121\) 个有效点，成功率较高。

Code

#include 
#define rep(i,a,b) for(int i(a);ib;--i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define pert(i,a,b) for(int i(a);i>=b;--i)
#define ll long long
#define eb emplace_back
using namespace std;
const int N=100,S=150,K=5;
const ll P=998244353;
ll ksm(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1) (res*=x)%=P;
        (x*=x)%=P,y>>=1;
    }
    return res;
}
vector Encode(vector vec){
    vector res;
    res.reserve(S*K);
    rept(x,1,S){
        ll y=0;
        pert(i,N-1,0) y=(y*x+vec[i])%P;
        rep(i,0,K) res.eb(y);
    }
    return res;
}
vector lagrange(const vector &x,const vector &y){
    int n=x.size();
    vector p(n+1,0),q(n+1,0),res(n,0);
    p[0]=1;
    rep(i,0,n){
        pert(j,i,0){
            (p[j+1]+=p[j])%=P;
            (p[j]*=-x[i])%=P;
        }
    }
    rep(i,0,n){
        ll a=1,rem=p[n];
        rep(j,0,n) if(i^j) (a*=x[i]-x[j])%=P;
        a=ksm(a,P-2)*y[i]%P;
        pert(j,n-1,0){
            q[j]=rem;
            (rem=p[j]+rem*x[i]%P)%=P;
        }
        rep(j,0,n) (res[j]+=a*q[j]%P)%=P;
    }
    rep(i,0,n) (res[i]+=P)%=P;
    return res;
}
vector Decode(vector vec){
    vector x,y;
    x.reserve(N),y.reserve(N);
    rept(i,1,S){
        map mp;
        rep(j,K*(i-1),K*i){
            ++mp[vec[j]];
            if(mp[vec[j]]>=2){
                x.eb(i),y.eb(vec[j]);
                break;
            }
        }
        if(x.size()>=N) break;
    }
    vector res=lagrange(x,y);
    return vector(res.begin(),res.end());
}