自动搬运

查看原文

来自洛谷，原作者为

	quantum11 **

搬运于2025-08-24 21:56:34，当前版本为作者最后更新于2018-12-02 22:25:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这道题其实很简单啊

三个变量时，把含有$x1$的项提出来:

$$f(x)=x1(a0x2x3+a1x2+a2x3+a4)+(a3x2x3+a5x2+a6x3+a7) $$

把$x1=1$和$x1=-1$代入，得到的两个柿子分别相加相减再除以$2$，就得到了两个只有原来一半规模的柿子，然后递归做就好了

输出很麻烦

#include<bits/stdc++.h>
#define il inline
#define rint register int
using namespace std;
int f[1<<21],n,a,b,mu,nn;char s[21];
il int gcd(rint x,rint y) {return y==0?x:gcd(y,x%y);}
il void get(){
	double c;rint t=0;
	scanf("%s %lf",s+1,&c);
	for(int i=1;i<=n;++i) t<<=1,t|=(s[i]=='+'?1:0);
	if(c>0) f[t]=(int)(c*100.0+0.5);
	else f[t]=(int)(c*100-0.5); 
}
il void p(rint x,rint y){
	if(x==0) return ;if(x<0) printf("-"),x=-x;
	rint t=gcd(x,mu);t==mu?printf("%d",x/mu):printf("%d/%d",x/t,mu/t);
	if(y!=0) printf(" ");for(int i=1;i<=n;++i,y<<=1) if(y&(nn>>1)) printf("x%d",i);
	putchar('\n');
}
il void OUT(rint s,rint x){
	int t=((x<<1)|1)<<(n-s);
	p(f[t],t);if(s==n) return;
	OUT(s+1,(x<<1)|1);OUT(s+1,(x<<1));
}
int main(){
	scanf("%d",&n);mu=100<<n;nn=1<<n;
	for(rint i=0;i<nn;++i) get();
	for(rint i=0;i<n;++i){
		rint d=1<<i;
		for(rint j=0;j<nn;j+=d*2) for(rint k=j;k<j+d;++k)
		a=f[k],b=f[k+d],f[k]=a+b,f[k+d]=b-a;
	}
	p(f[0],0);OUT(1,0);
	return 0;
}