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

· · 题解

Solution

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

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

1-\frac{\binom{K}{0}+\binom{K}{1}}{2^K}=1-\frac{1+K}{2^K}

最直接的想法是直接传原数组，每个数传 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 <bits/stdc++.h>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define per(i,a,b) for(int i(a);i>b;--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<int> Encode(vector<int> vec){
    vector<int> 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<ll> lagrange(const vector<ll> &x,const vector<ll> &y){
    int n=x.size();
    vector<ll> 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<int> Decode(vector<int> vec){
    vector<ll> x,y;
    x.reserve(N),y.reserve(N);
    rept(i,1,S){
        map<int,int> 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<ll> res=lagrange(x,y);
    return vector<int>(res.begin(),res.end());
}