通信题好玩。

Otomachi_Una_ · 2023-05-27 10:37:08 · 题解

通信题好玩。

基本的想法是每个数复制 7 次传进去。但是这样子一个数失败的概率已经大于达到 2^{-7}，我们有 10^6 个数这个概率显然接受不了。

我们想要把这 100 个数压缩在一起，随便得到 100 个值便可解码这原来的 100 个数。不难构造多项式 f(x)=\sum_{i=0}^{99} a_ix^i。对每个点值重复 5 次传进去。我们对连续的 5 个数，如果众数出现次数 \geq 2 那就取众数，否则丢弃这个点值。这样一个数失败的概率是 \dfrac{6}{32}，我们一共有 150 个数。成功率还是比较高的，在本机上跑大概 3\times 10^5 组数据才会出现问题。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define vint vector<int>
#define vl vector<long long>
#define vll vector<pair<long long,long long> >
int m=750,st=5,n=100;
const int MOD=998244353;
ll iv[355];
ll inv(ll a,int b=MOD-2){ll res=1;while(b){if(b&1)res=res*a%MOD;a=a*a%MOD,b>>=1;}return res;} 
vint lagr(vll a){
    vint res(n),f(n+1);
    if(!iv[n+1]){
        for(int i=-155;i<=155;i++)
            iv[i+160]=inv(i+MOD);
    }
    f[0]=1;
    for(int i=0;i<n;i++){// f*= (x-xi) 
        for(int j=n;j>=0;j--){
            f[j]=(MOD-a[i].first)*f[j]%MOD;
            if(j) f[j]=(f[j]+f[j-1])%MOD;           
        } 
    }
    for(int i=0;i<n;i++){
        ll c=a[i].second;
        for(int j=0;j<n;j++) if(i!=j) c=c*iv[a[i].first-a[j].first+160]%MOD;
        vint g(n+1);
        for(int j=n-1;j>=0;j--)
            g[j]=(f[j+1]+a[i].first*g[j+1])%MOD;
        for(int j=0;j<n;j++)
            res[j]=(res[j]+c*g[j])%MOD;
    }
    return res;
}
vint Decode(vint a){
    vll r;
    for(int i=1;i*st<=m;i++){
        map<int,int> M;
        for(int j=(i-1)*st;j<i*st;j++)
            M[a[j]]++;
        for(auto j:M) if(j.second>=2) r.push_back(MP(i,j.first));
    }
    assert(r.size()>=100);
    r.resize(100);
    return lagr(r);
}
vint Encode(vint a){
    auto f=[&](int x){
        ll ans=0;
        for(int i=n-1;i>=0;i--)
            ans=(ans*x+a[i])%MOD;
        return ans;
    };
    vint r;
    for(int i=1;i*st<=m;i++){
        int v=f(i);
        for(int j=1;j<=st;j++) r.push_back(v);
    }
    return r;
}