题解 P4106 【[HEOI2014]逻辑翻译 】

首先这题我们发现输入的是一种类似二进制数的东西，输出的也是一种类似二进制数的东西，我们把这两个玩意分析一下。 例如$n=3$的时候输入的会有$2^3$种+-的组合： ```cpp --- --+ -+- -++ +-- +-+ ++- +++ ``` 而输出的多项式也会有$2^3$种，不过这就跟上面的不一样了，它们相当于从全集$x_1x_2x_3$选出的所有子集： $1$ $x_1$ $x_2$ $x_3$ $x_1x_2$ $x_1x_3$ $x_2x_3$ $x_1x_2x_3$ 然后我们回归正题，考虑他让我们求的多项式： $f(x_1,x_2,x_3)=a_0+a_1x_1+a_2x_2+a_3x_3+a_4x_1x_2+a_5x_1x_3+a_6x_2x_3+a_7x_1x_2x_3$ 显然做这题从二进制位的角度为突破口是一个不错的选择。我们知道二进制数有个挺好的性质就是位是互相独立的对吧，假如我们当前在最高位，显然会有一半的二进制数在这一位是1，把这些数的最高位上的1剥掉之后就跟剩下的一半一模一样了。 我们把这东西的性质套到这个“二进制项”（这一项有这个变量，那一位就是1，否则就是0，也是相当于二进制数）的多项式里来，我们钦定$x_1$为最高位，那么把上面那个多项式变一下形就是： $f(x_1,x_2,x_3)=a_0+a_2x_2+a_3x_3+a_6x_2x_3+x_1(a_1+a_4x_2+a_5x_3+a_7x_2x_3)$ （如果你学过FFT或者FWT的话对这个应该是不会陌生的，没学过的建议去学一下再来做这题……） 咦，如果抛去$x_1$不管的话，我们就得到了两个形式一样的多项式？规模好像还减半了？ 那么很自然的就能想到一个递归分治的过程，我们递归到最底层只剩常数项的时候，这些系数就自然的出来了，甚至都不用回溯。 然而我们现在的问题是：如何“抛去$x_1$不管”？ 其实我们到现在为止还只利用了这题的一半性质，要知道，他给你的那堆关系里，$x_{\text{啥}}$的系数都是$1\space or\space -1$啊。 那么我们假设在递归的时候能够维护当前的这一堆关系，考虑咱们划分这个多项式的过程，左边的就不能有$x_1$，右边的虽然带着$x_1$但是跟没有一样，那么我们不妨把这堆关系也按照$x_1$划分一下，$x_1=1$的划成一堆，记为$A$，$x_1=-1$的划成一堆，记为$B$，然后我们将$x_1$分别代入，这个时候不考虑系数的话$B$的每一项都相当于$A$取反了，那么就把$\frac{A+B}{2}$就是把$x_1$的影响完全消掉了划到递归的左边去，把$\frac{A-B}{2}$就是把$x_1$的影响搞成1划到递归的右边去。 好，做完了。 另外这题的输出极为恶心，建议写个dfs输出，另外建议自行把$x_1,x_2……x_n$他们怎么进行二进制表示组织好，这题细节问题还是挺多的。 ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define abs(_o) ((_o<0)?-(_o):_o) #define ll long long using namespace std; namespace ywy{ inline int get(){ char c;int n=0; while((c=getchar())||23333)if(c=='-'||c=='+')break; n=(n<<1)|(c=='+'); while((c=getchar())||23333){ if(c=='+'||c=='-')n=(n<<1)|(c=='+'); else return(n); } } inline ll gcd(ll a,ll b){ if(a<0)a=-a; if(b<0)b=-b; while(b){ ll r=a%b;a=b;b=r; } return(a); } inline int Int(double n){ int down=(int)abs(n),up=down+1; if(abs(abs(n)-down)<abs(abs(n)-up))return((n<0)?-down:down); return((n<0)?-up:up); } void print(ll num){ if(num<0)putchar('-'),num=-num; if(num>=10)print(num/10); putchar(num%10+'0'); } typedef struct _fs{ ll a;ll b; _fs(){}_fs(ll i,ll j){a=i;b=j;} _fs(double n){ a=Int(n*100);b=100;wh(); } friend _fs operator *(const _fs &a,const _fs &b){ ll cjr=a.a*b.a,ywy=a.b*b.b; ll r=gcd(cjr,ywy); cjr/=r;ywy/=r; return(_fs(cjr,ywy)); } inline void wh(){ ll r=gcd(a,b);a/=r;b/=r; if(b<0)a=-a,b=-b; } friend _fs operator /(const _fs &a,const int &b){ _fs cjr=a;cjr.b*=b; cjr.wh();return(cjr); } friend _fs operator +(const _fs &a,const _fs &b){ _fs cjr=_fs(a.a*b.b+b.a*a.b,a.b*b.b);cjr.wh();return(cjr); } friend _fs operator -(const _fs &a,const _fs &b){ _fs cjr=_fs(a.a*b.b-b.a*a.b,a.b*b.b);cjr.wh();return(cjr); } inline void print(){ wh();if(b==1)ywy::print(a);else ywy::print(a),putchar('/'),ywy::print(b); } }fs;fs poly[1048577]; inline void fwt(int n){ for(register int bit=n;bit>1;bit>>=1){ for(register int i=0;i<n;i+=bit){ for(register int j=i;j<i+(bit>>1);j++){ fs ywy=poly[j],cjr=poly[j+(bit>>1)]; poly[j]=(ywy+cjr)/2; poly[j+(bit>>1)]=(cjr-ywy)/2; } } } } int n; inline void pr(int id){ int cnt=1;for(register int i=n-1;i>=0;i--){ if(id&(1<<i))putchar('x')，print(cnt);cnt++; } } unsigned char printed[1049576]; void dfs(int now,int deep,unsigned char is1){ if(deep==-1){ if(poly[now].a&&!printed[now]){ poly[now].print();putchar(' ');pr(now);putchar('\n')； } printed[now]=1;return； }if(is1&&!printed[now]){ printed[now]=1; if(poly[now].a){ poly[now].print();putchar(' ');pr(now);putchar('\n'); } } dfs(now|(1<<deep),deep-1,1); dfs(now,deep-1,0); } void ywymain(){ cin>>n;for(register int i=0;i<(1<<n);i++){ int id=get();double d;scanf("%lf",&d);poly[id]=_fs(d); } fwt(1<<n);dfs(0,n-1,1)； } } int main(){ ywy::ywymain();return(0);//再见程序 } ```