题目大意

　　这是一道通信题。

　　给你 \(8\) 个 \(32\) 位整数。加密端要把这些数加密成至少 \(1000\) 个 \(32\) 位整数，交互库会把这些整数随机打乱后发给解密端，解密端最多能获得其中 \(lim\) 个的值，解密端要按顺序给出这 \(8\) 个整数。

　　交互库会测试 \(100\) 次。

　　对于 \(lim\geq 50\) 的测试点，要求 \(100\%\) 的正确率。

　　对于 \(lim\geq 20\) 的测试点，要求 \(90\%\) 的正确率。

　　对于 \(lim\geq 17\) 的测试点，要求 \(50\%\) 的正确率。

题解

解法一

　　先把这些数拆成 \(16\) 个 \(16\) 位整数。

　　然后每次随机选一些数异或到一起，前 \(16\) 位为这些数的异或值，后 \(16\) 位为选了那些数。

　　解密端随机 \(lim\) 个数，求出这些数能不能解出原来的 \(16\) 个数。

　　如果 \(lim\times 16\) 的矩阵满秩就能求出。

　　\(17\times 16\) 的矩阵满秩的概率约为 \(58\%\)。

　　\(20\times 16\) 的矩阵满秩的概率约为 \(94\%\)。

　　\(50\times 16\) 的矩阵满秩的概率约为 \(100\%\)。

解法二

　　还是先把这些数拆成 \(16\) 个 \(16\) 位整数，记为 \(a_0,a_1,\ldots,a_{15}\)。

　　记 \(f(x)=\sum_{i=0}^{15}a_ix^i\)。

　　取一个合适大小的整数 \(p\)。

　　对于 \(0\leq i<1000\)，返回 \(i+(f(i)\bmod p)\times 1000\)。

　　解密端随便选 \(16\) 个数就能插值插出 \(a_0,a_1,\ldots,a_{15}\)。

　　正确率为 \(100\%\)。

代码

解法一

#include<vector>

#include<algorithm>

using namespace std;

vector<int>encode(vector<int>arr,int lim)

{

	static unsigned a[100];

	for(int i=0;i<16;i++)

		a[i]=0;

	for(int i=0;i<8;i++)

	{

		unsigned v=arr[i];

		a[i*2]=v&((1<<16)-1);

		a[i*2+1]=v>>16;

	}

	for(int i=0;i<16;i++)

		a[i]|=1<<(i+16);

	vector<int>vec;

	for(int i=0;i<1<<16;i++)

	{

		unsigned s=0;

		for(int j=0;j<16;j++)

			if((i>>j)&1)

				s^=a[j];

		vec.push_back(s);

	}

	return vec;

}

static unsigned seed=1932532;

static unsigned get()

{

	seed^=seed<<13;

    seed^=seed>>17;

    seed^=seed<<5;

    return seed;

}

vector<int>decode(int(*const arr)(int),int n,int lim){

	static unsigned a[100],b[1000000],c[1000000];

	for(int i=0;i<1<<16;i++)

		c[i]=i;

	for(int i=0;i<1<<16;i++)

	{

		int y=get()%(i+1);

		if(y!=i)

			swap(c[i],c[y]);

	}

	for(int i=0;i<lim;i++)

		b[i]=arr(c[i]);

	vector<int>vec;

	for(int i=0;i<16;i++)

	{

		int x=lim;

		for(int j=i;j<lim;j++)

			if(b[j]&(1<<(16+i)))

			{

				x=j;

				break;

			}

		if(x>=lim)

		{

			for(int i=0;i<8;i++)

				vec.push_back(0);

			return vec;

		}

		if(x!=i)

			swap(b[x],b[i]);

		for(int j=0;j<lim;j++)

			if(j!=i&&(b[j]&(1<<(16+i))))

				b[j]^=b[i];

	}

	for(int i=0;i<16;i++)

		b[i]&=(1<<16)-1;

	for(int i=0;i<8;i++)

		vec.push_back((b[i*2+1]<<16)|b[i*2]);

	return vec;

}

解法二

#include<vector>

#include<algorithm>

using namespace std;

typedef long long ll;

static const ll p=100003;

vector<int>encode(vector<int>arr,int lim)

{

	static unsigned a[100];

	for(int i=0;i<16;i++)

		a[i]=0;

	for(int i=0;i<8;i++)

	{

		unsigned v=arr[i];

		a[i*2]=v&((1<<16)-1);

		a[i*2+1]=v>>16;

	}

	vector<int> vec;

	for(int i=0;i<1000;i++)

	{

		ll s=0;

		for(int j=15;j>=0;j--)

			s=(s*i+a[j])%p;

		vec.push_back(i+s*1000);

	}

	return vec;

}

static ll fp(ll a,ll b)

{

	ll s=1;

	for(;b;b>>=1,a=a*a%p)

		if(b&1)

			s=s*a%p;

	return s;

}

vector<int>decode(int(*const arr)(int),int n,int lim){

	static unsigned a[100],b[100];

	static ll x[1000],y[1000],ans[1000],e[1000];

	for(int i=0;i<16;i++)

	{

		b[i]=arr(i);

		x[i]=b[i]%1000;

		y[i]=b[i]/1000;

	}

	for(int i=0;i<16;i++)

		ans[i]=0;

	for(int i=0;i<16;i++)

	{

		for(int j=0;j<16;j++)

			e[j]=0;

		e[0]=1;

		for(int j=0;j<16;j++)

			if(j!=i)

			{

				for(int k=15;k>=0;k--)

				{

					e[k+1]=(e[k+1]+e[k])%p;

					e[k]=-e[k]*x[j]%p;

				}

			}

		ll s=y[i];

		for(int j=0;j<16;j++)

			if(j!=i)

				s=s*fp(x[i]-x[j],p-2)%p;

		for(int j=0;j<16;j++)

		{

			e[j]=e[j]*s%p;

			ans[j]=(ans[j]+e[j])%p;

		}

	}

	for(int i=0;i<16;i++)

		a[i]=(ans[i]+p)%p;

	vector<int>vec;

	for(int i=0;i<8;i++)

		vec.push_back((a[i*2+1]<<16)|a[i*2]);

	return vec;

}