#810. 「UNR #7」比特迷宫

神秘随机化。

题目简介

题目名称： 比特迷宫

题目来源：

评测链接：https://uoj.ac/problem/810

形式化题意：给定一个 次多项式 ，保证 ，你可以进行不多于 操作，每次操作形如一个二元组 ，将这个多项式加上：

$$x^a(1+x)^b$$

并在每次操作结束后执行 ，请构造一个方案使操作结束后所有 。

数据范围：

神秘题，现在还不清楚正解是什么，但大多数过了的人都是高级随机化，后来也有很多被 掉，但是还是剩了不少优秀的随机化算法。

首先考虑简化题意：

$$\begin{align} x^a(1+x)^b&=\nonumber \sum_{i=0}^{b}\binom{b}{i}x^{a+b-i} \end{align}$$

根据 定理，我们知道：

$$\binom{b}{i}\bmod 2=\binom{\lfloor\frac{b}{2}\rfloor}{\lfloor\frac{i}{2}\rfloor}\cdot\binom{b\bmod 2}{i\bmod 2}\bmod 2$$

容易发现，这个式子只有在 同时含有质因子 或者同时不含有的时候才会成立，以此类推，直到 ， 前面的二进制位都应该是相同的。

也就是当 时，，否则 。

那我们转化题意为，给定二元组 ，对所有的 ，将 取反。

我们了解 ，所以我们每一次操作至少要改 个 才能保证操作次数。

但我偏不！我首先随机一坨 出来修改，让 的个数尽可能小，然后每次修改 个，枚举 修改 ，然后就可以了。

为啥能过？我也不知道甚至 只跑了 ，绰绰有余，不知道为啥，挺玄学的，时间也卡不满。

AC Code

// ----- Eternally question-----
// Problem: B. 比特迷宫
// Contest: UOJ - UOJ NOI Round #7 Day1
// URL: https://uoj.ac/contest/84/problem/810
// Memory Limit:  1024 MB
// Time Limit: 6000 ms
// Written by: Eternity
// Time: 2023-07-16 08:16:50
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
const int MAXN=1<<20|10;
int N,K,T,v[MAXN];
std::vector<Pir>vec;
std::mt19937 rnd((ll)new char);
inline void calc(int a,int b)
{
	vec.push_back({a,b});
	for(int s=b;s;s=(s-1)&b) v[a+s]^=1;
	v[a]^=1;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,K,T);
	for(int i=0;i<N;++i) read(v[i]);
	for(int i=1000;i;--i)
	{
		int a=rnd()%N,b=rnd()%(N-a);
		calc(a,b);
	}
	int cnt=0;
	for(int i=0;i<N;++i) cnt+=v[i];
	for(int i=0;i<N;++i)
	{
		if(!v[i]) continue;
		for(int j=0;j<K;++j)
		{
			if(!v[i]) break;
			if(i+(1<<j)>=N||!v[i+(1<<j)]) continue;
			for(int k=j+1;k<K;++k) if(i+(1<<j)+(1<<k)<N&&v[i+(1<<k)]&&v[i+(1<<j)+(1<<k)])
			{
				calc(i,(1<<j)|(1<<k));
				break;
			}
		}
		if(v[i]) calc(i,0);
	}
	write(vec.size(),'\n');
	for(auto x:vec) write(x.fir,' ',x.sec,'\n');
	return 0;
}