最近我博客似乎出了点 bug，倒是不太会修，将就着看吧。

本文主要关注第四个子任务，前面三个有叙述不清的敬请谅解。

UOJ354 新年的投票

Sub1

不管人的编号直接爆搜就能够找到一个合法方案。

Sub3

第 \(i\) 个人假设自己是第一个 \(1\)，\(1\sim i-1\) 的都不能是 \(1\)，如果自己确实有这个可能，给自己视角内的正确值投出 \(2^i\) 票，把前面所有人的票无效掉，否则不投票。

这样子只会有最低位的 \(1\) 的票有效，而他假设自己是 \(1\)，能够投出正确值，唯一错误的情况是不存在 \(1\) 的全 \(0\) 情况。

Sub2

把 \(15\) 个人分成 \(1,2,4,8\) 四组套用 Sub3 做法即可。

错误的情况只有四组内部的答案均为 \(0\)，算一下容易得到情况数是 \(2048\) 种可以通过。

Sub4

考虑一个人的视角用向量表示，看到的 \(k\) 个分别是 \(x_1,x_2,\cdots,x_k\)。

如果我们有一个关于上述向量的函数 \(f\)，它是一个整系数 \(k\) 次多项式，那么我们可以把其中的某项交给能够看到这些项的人投出其系数。

刚刚那句话很抽象，我们详细解释一下。

首先明确 \(f(\boldsymbol{v})\) 表示实际串为 \(\boldsymbol{v}\) 时，最后应该投出的总票数，我们设给奇数投票为正，偶数为负。

这里 \(\boldsymbol{v}\) 是一个 \(n\) 维向量而非 \(k\) 维向量，这个向量的每一维都是 \(0\) 或 \(1\)，不妨设 \(\boldsymbol{v}=\{x_1,x_2,\cdots,x_n\}\)。

假设 \(f\) 中有一项 \(-3x_1x_3x_5\)，那么我们可以让一个能看到 \(x_1,x_3,x_5\) 的人来根据这三个变量的值决定是否投出 \(-3\) 票。

注意只能让一个人投，多个人都投会导致重复，此时如果想要让最后的答案式子的系数依旧是整数就很容易超过 \(10^8\) 的限制。

这之后我们再考虑 \(s=\sum\limits_{i=1}^{k}x_i\)，投票的目的就是找出 \(s\) 的奇偶性。

所以我们尝试找到一个关于 \(s\) 的多项式 \(g(s)\)，我们令其也为一个 \(k\) 次多项式，则其最多有 \(k\) 个零点。

这个多项式的目标是在尽可能多的地方得到正确的正负性，因此需要找到适合的零点拐弯。

经过一些计算你可以得到最优的情况是在 \(0,2,11\) 得到错误的正负性（或者反过来 \(12,1,10\) 也是一样的）。

此时错误的数量可以计算，为 \(\dbinom{12}{0}+\dbinom{12}{2}+\dbinom{12}{11}=79\) 种，正好符合要求。

写出 \((x-p_1)\times\cdots\times(x-p_k)\) 这样的式子，将 \(p_i=2.5+i\) 代入得到化简后的式子。

乘上 \(-128\) 变成整系数后的式子是：

\(-128x^7+5824x^6-111776x^5+1172080x^4-7246232x^3+26389636x^2-52371534x+43648605\)

可以看到确实控制在 \(10^8\) 的限制内，并且比较极限。

接下来考虑怎么把这个式子分给每个人投票，即把 \(g(s)\) 和 \(f(\boldsymbol{v})\) 关联起来。

回顾定义，\(s=\sum\limits_{i=1}^k x_i\)。

将其代入，得到的也是一个 \(k\) 次多项式，即我们要求的 \(f\)。

系数并不会炸，最大也就是对应次幂的系数乘上对应次数的阶乘，目测一下就知道活得好好的。

这东西你就慢慢折磨去吧，总是能搞出来的，毕竟提答题不用考虑时间复杂度，写个爆搜也是可以的。

具体实现不讲留给读者思考，也可以参考示例代码。

Code

#include<bits/stdc++.h>
using namespace std;
#define __FILE_MODE__
namespace Task_1
{
	//懒得写了，直接看 Task2。
	//爆搜的思路就是根据看到的 $0$ 和 $1$ 的个数做出决策。
	//可以搜出 6906 种错误情况的策略，似乎还有更优一点的但不重要。
}
namespace Task_2
{
	constexpr int N=15;
	int ans[N][1<<N];
	inline int group(int x)//判断 x 是哪个组的。
	{
		if(x<1)return 1;
		if(x<3)return 2;
		if(x<7)return 3;
		if(x<15)return 4;
        return -1;
	}
	inline void work(int n)
	{
#ifdef __FILE_MODE__
		freopen("vote2.ans","w",stdout);
#endif
		if((n+1)&n){printf("Invalid!");return;}//此策略仅对 $n=2^k-1$ 有效。
		for(int S=0;S<(1<<(n-1));S++)
		{
			for(int i=0;i<n;i++)
			{
				bool fl=true;//判断前面是否全 0 的旗子。
				int gr=group(i);
				for(int j=1;j<gr;j++)
				{
					int sum=0;
					for(int k=0;k<(1<<j)-1;k++)
					{
						if(group(k)!=j)continue;
						sum^=(S>>k)&1;
					}
					if(sum!=0)fl=false;
				}
				if(fl)
				{
					int res=0;
					for(int j=gr+1;j<=4;j++)
					{
						int sum=0;
						for(int k=(1<<(j-1))-1;k<(1<<j)-1;k++)sum^=(S>>(k-1))&1;
						res^=sum;
					}
					ans[i][S]=res^1;
				}
				else ans[i][S]=i&1;
			}
		}
		for(int i=0;i<n;i++)
		{
			for(int S=0;S<(1<<(n-1));S++)printf("%d",ans[i][S]);
			putchar(10);
		}
		return;
	}
}
namespace Task_3
{
	constexpr int N=15;
	int ans[N][1<<N];
	inline void work(int n)
	{
#ifdef __FILE_MODE__
		freopen("vote3.ans","w",stdout);
#endif
		for(int S=0;S<(1<<(n-1));S++)
		{
			for(int i=0;i<n;i++)
			{
				bool fl=true;//判断前面是否全 0 的旗子。
				for(int j=0;j<i;j++)if((S>>j)&1)fl=false;
				if(fl)
				{
					int res=0;
					for(int j=i;j<n-1;j++)res^=(S>>j)&1;
					if(res)ans[i][S]=-(1<<i);else ans[i][S]=(1<<i);
				}
				else ans[i][S]=0;
			}
		}
		for(int i=0;i<n;i++)
		{
			for(int S=0;S<(1<<(n-1));S++)printf("%d ",ans[i][S]);
			putchar(10);
		}
		return;
	}
}
namespace Task_4
{
	constexpr int N=12,K=7;
	constexpr int p[K+1]={43648605,-52371534,26389636,-7246232,1172080,-111776,5824,-128};
	constexpr int NUM=792;//共有 C(12,7)=792 人。
	int ans[NUM][1<<K];
	int sight[NUM],rev[1<<N];//每个人看到的实际编号。
	int bel[1<<N];//预处理出出现该情况时给谁投。
	inline int func(int sight,int fact)//处理出这个人的实际所见。
	{
		int ret=0,tot=0;
		for(int i=0;i<N;i++)if((sight>>i)&1)ret|=((fact>>i)&1)<<tot,tot++;
		return ret;
	}
	inline int ppc(int V)
	{
		int s=0;
		for(int i=0;i<N;i++)s+=(V>>i)&1;
		return s;
	}
	void DFS(int now,int pw)
	{
		if(pw>K)return;//次数过大。
		int id=bel[now];
		int unchanged=func(sight[id],now);
		for(int S=0;S<(1<<K);S++)if((S&unchanged)==unchanged)ans[id][S]+=p[pw];
		for(int i=0;i<N;i++)DFS(now|(1<<i),pw+1);
		return;
	}
	inline void work(int n,int k)
	{
#ifdef __FILE_MODE__
		freopen("vote4.ans","w",stdout);
#endif
		if(n!=12||k!=7)return;//此策略仅对 $n=12,k=7$ 有效。
		int tot=0;
		for(int V=0;V<(1<<n);V++)
		{
			int s=ppc(V);
			if(s==k)
			{
				sight[tot]=V;
				rev[V]=tot;
				tot++;
			}
			else rev[V]=-1;
		}
		for(int V=0;V<(1<<n);V++)
		{
			int s=ppc(V);
			if(s>k)continue;
			for(int i=0;i<NUM;i++){if((sight[i]&V)==V){bel[V]=i;break;}}
		}
		DFS(0,0);
		for(int i=0;i<NUM;i++)
		{
			for(int S=0;S<(1<<k);S++)printf("%d ",ans[i][S]);
			putchar(10);
		}
		return;
	}
}
int main()
{
	Task_2::work(15);
	Task_3::work(15);
	Task_4::work(12,7);
	return 0;
}

完整文件有 1197.5kb 就不贴了，上面那个程序可以直接运行出来。