题解：P6678 [COCI 2019/2020 #2] Popcount

题目大意

你需要制定一个操作序列，可以包含 $+,-,\&,|,<<,>>$，即加，减，按位与，按位或，左移，右移六种运算符。要求对一个非负数 $A$ 执行操作序列让 $A$ 变为 $\operatorname{popcount(A)}$，即 $\texttt{A}$ 在二进制下的 1 的个数。这个非负整数的范围是 $[0,2^n-1]$。操作序列的每条操作形如 $\texttt{A=<expr>}$，其中 $\texttt{<expr>}$ 可以为 $\texttt{A}$ 或 $\texttt{<num>}$，一个非负十进制整数，或 $\texttt{<expr><operator><expr>}$，其中 $\texttt{<operator>}$ 为上文提到的六种运算符之一。

$\texttt{<expr>}$ 中出现 $\texttt{A}$ 的次数不能超过 5 次。每条操作不能超过 $10^3$ 个字符。操作序列数不超过 $k$。

Subtask1

注：作者为了表示简洁下文中的操作可能不按题目要求写，注意提交时要保证所有运算都加上括号，作者可能会省略。

由于 $k=n-1$，所以计算 $\operatorname{popcount}$ 可以直接枚举 $A$ 的每一位，即 $\texttt{A=A-(A\&(1<<i))+(A\&(1<<i)>>i)}$，相当于减去这一位再加上这一位的贡献，让 $i$ 从小到大枚举答案就不会与未统计的位发生冲突。

Subtask1代码

	if(k>=n-1){
		cout<<n-1<<'\n';
		for(int i=1;i<n;i++){
			cout<<"A=((A-(A&(1<<"<<i<<")))+((A&(1<<"<<i<<"))>>"<<i<<"))\n";
		}
	}

Subtask2

注意到Subtask1中一次操作只能统计一位的贡献，效率很低，考虑如何一次操作多统计几位。

根据Subtask1的思路，相当于先将一位从 $A$ 中减掉再加上这一位的贡献，其中减去一位可以优化为 $\texttt{A\&((0-1)-(1<<i))}$，只用了一个 $A$，那么后面就可以有 4 个 $A$，一次统计 4 个数的贡献，即 $\texttt{A\&((0-1)-(1<<i)-(1<<i+1)-(1<<i+2)-(1<<i+3))+((A>>i)\&1)+((A>>i+1)\&1)+((A>>i+2)\&1)+((A>>i+3)\&1)}$

Subtask2代码

	if(n==500&&k==128){
		cout<<125<<'\n';
		for(int i=1;i<n;i+=4){
			cout<<"A=(((A&(((((0-1)-(1<<"<<i<<"))-(1<<"<<i+1<<"))-(1<<"<<i+2<<"))-(1<<"<<i+3<<")))+((A>>"<<i<<")&1))+((((A>>"<<i+1<<")&1)+((A>>"<<i+2<<")&1))+((A>>"<<i+3<<")&1)))\n";
		}
	}

Subtask3

现在题目要求 $k \le \log_2 n$，可以运用类似线段树的思想：

先把 $A$ 的二进制数位划分成若干给长度为 $2^0$ 的段，此时单看每个段内的数就是每个段内的答案，然后将相邻的段合并为长度为 $2^1$ 的段，其中的数即为原本的两个段的答案之和，然后以此类推，直到合并到段的长度大于等于 $n$ 就是答案。

具体的写法就是先将当前的 $A$ 分成若干个长为 $2_i$ 的段，并将其交替分为两个部分，再让靠后的部分右移 $2^i$ 位，即与对应的前一个段重合，再相加就是答案。

变成操作就是 $\texttt{(A\&(1<<0+1<<1+1<<4))+(A\&(1<<2+1<<3))>>(1>>0)}$（以 $n=5$，段长为 $2^1$ 为例）。

Subtask3代码

	else if(k==7){
		int pp=1,cnt=0;
		while(pp<n){
			cnt++;pp<<=1;
		}
		cout<<cnt<<'\n';
		int len=1,p=0;
		for(int i=1;len<n;i++){
			cout<<"A=((A&";
			vector<int> v;
			int u=0;
			while(u<n){
				for(int j=0;j<len;j++){
					v.push_back(u);u++;
					if(u==n)break;
				}
				u+=len;
			}
			for(int j=1;j<v.size();j++)cout<<"(";
			for(int j=0;j<v.size();j++){
				cout<<"(1<<"<<v[j]<<")";
				if(j)cout<<")";
				if(j<v.size()-1)cout<<"+";
			}
			cout<<")+((A&";
			v.clear();
			u=len;
			while(u<n){
				for(int j=0;j<len;j++){
					v.push_back(u);u++;
					if(u==n)break;
				}
				u+=len;
			}
			for(int j=1;j<v.size();j++)cout<<"(";
			for(int j=0;j<v.size();j++){
				cout<<"(1<<"<<v[j]<<")";
				if(j)cout<<")";
				if(j<v.size()-1)cout<<"+";
			}
			cout<<")>>(1<<"<<p<<")))\n";
			len<<=1;p++;
		}
	}

Subtask4

看着 $100 \le n \le 500,k=10$ 可以用Subtask3的方法过，但题目要求一条操作长度不能超过 $10^3$ 个字符，显然会超。

注意到题目并没有限制 $\texttt{<num>}$ 的大小，所以我们可以把原本的 $\texttt{(1<<x)+(1<<y)+(1<<z)...}$ 用数字表示就不会过长了，不过要写高精度

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9;
struct N{
	ll a[110],n;
	N(){
		memset(a,0,sizeof(a));
		n=0;
	}
};
N cheng(N a,ll v){
	N b;
	for(int i=1;i<=a.n;i++){
		b.a[i]=a.a[i]*v;
	}
	b.n=a.n;
	for(int i=1;i<=b.n;i++){
		b.a[i+1]+=b.a[i]/mod;
		b.a[i]%=mod;
		if(i==b.n&&b.a[i+1])b.n++;
	}
	return b;
}
N jia(N a,N b){
	N c;
	c.n=max(a.n,b.n);
	for(int i=1;i<=c.n;i++){
		c.a[i]=a.a[i]+b.a[i];
	}
	for(int i=1;i<=c.n;i++){
		c.a[i+1]+=c.a[i]/mod;
		c.a[i]%=mod;
		if(c.a[i+1]&&i==c.n)c.n++; 
	}
	return c;
}
N pow(ll b){
	N a;
	a.n=1;a.a[1]=1;
	while(b--)a=cheng(a,2);
	return a;
}
void pr(N a){
	for(int j=a.n;j;j--){
		int len=to_string(a.a[j]).size();
		while(j!=a.n&&len<9){
			cout<<0;len++;
		}
		cout<<a.a[j];
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,k;
	cin>>n>>k;
	if(n==1){
		cout<<"0\n";
		return 0;
	}
	if(k>=n-1){//Subtask1
		cout<<n-1<<'\n';
		for(int i=1;i<n;i++){
			cout<<"A=((A-(A&(1<<"<<i<<")))+((A&(1<<"<<i<<"))>>"<<i<<"))\n";
		}
	}
	else if(n==500&&k==128){//Subtask2
		cout<<125<<'\n';
		for(int i=1;i<n;i+=4){
			cout<<"A=(((A&(((((0-1)-(1<<"<<i<<"))-(1<<"<<i+1<<"))-(1<<"<<i+2<<"))-(1<<"<<i+3<<")))+((A>>"<<i<<")&1))+((((A>>"<<i+1<<")&1)+((A>>"<<i+2<<")&1))+((A>>"<<i+3<<")&1)))\n";
		}
	}
	else if(k==7){//Subtask3
		int pp=1,cnt=0;
		while(pp<n){
			cnt++;pp<<=1;
		}
		cout<<cnt<<'\n';
		int len=1,p=0;
		for(int i=1;len<n;i++){
			cout<<"A=((A&";
			vector<int> v;
			int u=0;
			while(u<n){
				for(int j=0;j<len;j++){
					v.push_back(u);u++;
					if(u==n)break;
				}
				u+=len;
			}
			for(int j=1;j<v.size();j++)cout<<"(";
			for(int j=0;j<v.size();j++){
				cout<<"(1<<"<<v[j]<<")";
				if(j)cout<<")";
				if(j<v.size()-1)cout<<"+";
			}
			cout<<")+((A&";
			v.clear();
			u=len;
			while(u<n){
				for(int j=0;j<len;j++){
					v.push_back(u);u++;
					if(u==n)break;
				}
				u+=len;
			}
			for(int j=1;j<v.size();j++)cout<<"(";
			for(int j=0;j<v.size();j++){
				cout<<"(1<<"<<v[j]<<")";
				if(j)cout<<")";
				if(j<v.size()-1)cout<<"+";
			}
			cout<<")>>(1<<"<<p<<")))\n";
			len<<=1;p++;
		}
	}
	else{//Subtask4
		int pp=1,cnt=0;
		while(pp<n){
			cnt++;pp<<=1;
		}
		cout<<cnt<<'\n';
		int len=1,p=0;
		for(int i=1;len<n;i++){
			cout<<"A=((A&";
			vector<int> v;
			int u=0;
			N s;
			while(u<n){
				for(int j=0;j<len;j++){
					s=jia(s,pow(u));u++;
					if(u==n)break;
				}
				u+=len;
			}
			pr(s);
			cout<<")+((A&";
			v.clear();
			memset(s.a,0,sizeof(s.a));
			s.n=0;
			u=len;
			while(u<n){
				for(int j=0;j<len;j++){
					s=jia(s,pow(u));u++;
					if(u==n)break;
				}
				u+=len;
			}
			pr(s);
			cout<<")>>(1<<"<<p<<")))\n";
			len<<=1;p++;
		}
	}
	return 0;
}