自动搬运

查看原文

来自洛谷，原作者为

	Otomachi_Una_ We will never forget those days, thanks for everything.

搬运于2025-08-24 22:45:57，当前版本为作者最后更新于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;
}