【题解】代数正规型

题意

代数正规型ANF可以用来描述一个真值表，其统一格式为
其中这里的+表示异或操作，表示两个变量按位与操作。
现在给你真值表，请你将这个ANF输出出来。

题解

这题按照题意进行模拟即可，由于，所以系数最多只有16个，我们可以利用dfs或者利用二进制枚举子集去枚举的状态为0还是1。若某次枚举能让整个真值表符合，那么就说明找到了正确的系数。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int y[N];
int a[N];
int n;
map<int,string>vis;
vector<string>str[5];
int check(int v)
{
    int x[n];
    for(int i=0; i<n; i++)
        x[i]=(v>>i)&1;
    if(n==2)
    {
        return (a[0])^(a[1]*x[0])^(a[2]*x[1])^(a[3]*(x[0]&x[1]));
    }
    else if(n==3)
    {
        return (a[0])^(a[1]*x[0])^(a[2]*x[1])^(a[3]*x[2])^(a[4]*(x[0]&x[1]))^(a[5]*(x[0]&x[2]))^(a[6]*(x[1]&x[2]))^(a[7]*(x[0]&x[1]&x[2]));
    }
    else
    {
        return (a[0])^(a[1]*x[0])^(a[2]*x[1])^(a[3]*x[2])^(a[4]*x[3])^(a[5]*(x[0]&x[1]))^(a[6]*(x[0]&x[2]))^(a[7]*(x[0]&x[3]))^(a[8]*(x[1]&x[2]))^(a[9]*(x[1]&x[3]))^(a[10]*(x[2]&x[3]))^(a[11]*(x[0]&x[1]&x[2]))^(a[12]*(x[0]&x[1]&x[3]))^(a[13]*(x[0]&x[2]&x[3]))^(a[14]*(x[1]&x[2]&x[3]))^(a[15]*(x[0]&x[1]&x[2]&x[3]));
    }
}
void init()
{
    vis[0]="x[0]";
    vis[1]="x[1]";
    vis[2]="x[2]";
    vis[3]="x[3]";
    str[2].push_back("1");
    str[3].push_back("1");
    str[4].push_back("1");
    for(int i0=0; i0<3; i0++)
        str[2].push_back(vis[i0]);
    str[2].push_back(vis[0]+vis[1]);
    for(int i0=0; i0<3; i0++)
        str[3].push_back(vis[i0]);
    for(int i0=0; i0<3; i0++)
        for(int i1=i0+1; i1<3; i1++)
            str[3].push_back(vis[i0]+vis[i1]);
    str[3].push_back(vis[0]+vis[1]+vis[2]);
    for(int i0=0; i0<4; i0++)
        str[4].push_back(vis[i0]);
    for(int i0=0; i0<4; i0++)
        for(int i1=i0+1; i1<4; i1++)
            str[4].push_back(vis[i0]+vis[i1]);
    for(int i0=0; i0<4; i0++)
        for(int i1=i0+1; i1<4; i1++)
            for(int i2=i1+1; i2<4; i2++)
                str[4].push_back(vis[i0]+vis[i1]+vis[i2]);
    str[4].push_back(vis[0]+vis[1]+vis[2]+vis[3]);
}
int main()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(y,0,sizeof(y));
        scanf("%d",&n);
        for(int i=0; i<(1<<n); i++)
        {
            scanf("%d",&y[i]);
        }
        for(int i=0; i<(1<<(1<<n)); i++)
        {
            for(int j=0; j<(1<<n); j++)
            {
                if(i&(1<<j))
                {
                    a[j]=1;
                }
                else
                    a[j]=0;
            }
            int flag=0;
            for(int j=0; j<(1<<n); j++)
                if(y[j]!=check(j))
                {
                    flag=1;
                    break;
                }
            if(!flag)
            {
                for(int j=0; j<(1<<n); j++)
                    if(a[j])
                        cout<<str[n][j]<<" ";
                if(i==0)
                    printf("0");
                printf("\n");
                break;
            }
        }
    }
    return 0;
}