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

quantum11 · 2018-12-02 22:25:24 · 题解

这道题其实很简单啊

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

把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;
}