联考20200721 T1 s1mple

分析：
大佬博客膜了膜了
扑通扑通跪下来

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<string>

#define maxn 18
#define INF 0x3f3f3f3f
#define MOD 998244353

using namespace std;

inline int getint()
{
	int num=0,flag=1;char c;
	while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
	while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
	return num*flag;
}

int n,Q;
long long f[maxn][1<<maxn],g[1<<maxn][maxn],sz[1<<maxn];
long long a[1<<maxn],ans[1<<maxn];
char s[maxn];
int c[maxn][maxn];
vector<int>tmp;

inline int solve(int x)
{
	int t=0;tmp.clear();
	for(int i=n-2;~i;--i){t++;if(((x>>i)&1)==0)tmp.push_back(t),t=0;}
	tmp.push_back(t+1);
	sort(tmp.begin(),tmp.end());
	int num=0;
	for(int i=0;i<tmp.size();i++)num=(num<<tmp[i])+((1<<tmp[i]-1)-1); 
	return num;
}

inline void FWT(long long *a,int n)
{
	for(int i=1;i<n;i<<=1)for(int j=0;j<n;j+=i<<1)
		for(int k=j;k<j+i;k++)a[k+i]+=a[k];
}
inline void IFWT(long long *a,int n)
{
	for(int i=1;i<n;i<<=1)for(int j=0;j<n;j+=i<<1)
		for(int k=j;k<j+i;k++)a[k+i]-=a[k];
}

int main()
{
	n=getint();
	for(int i=0;i<n;i++)
	{
		scanf("%s",s);
		for(int j=0;j<n;j++)c[i][j]=s[j]-48;
	}
	f[0][0]=1;
	for(int i=0;i<(1<<n);i++)
	{
		sz[i]=sz[i>>1]+(i&1);
		for(int j=0;j<n;j++)if(i&(1<<j))
		{
			int t=i^(1<<j);
			if(!t)g[i][j]=1;
			for(int k=0;k<n;k++)if(c[j][k])g[i][j]+=g[t][k];
			f[sz[i]][i]+=g[i][j];
		}
	}
	for(int i=0;i<=n;i++)FWT(f[i],1<<n);
	memset(ans,-1,sizeof ans);
	for(int i=0;i<(1<<(n-1));i++)
	{
		int t=solve(i);
		if(~ans[t]){ans[i]=ans[t];continue;}
		for(int j=0;j<(1<<n);j++)a[j]=1;
		for(int j=0;j<tmp.size();j++)
			for(int k=0;k<(1<<n);k++)a[k]*=f[tmp[j]][k];
		IFWT(a,1<<n);
		ans[i]=ans[t]=a[(1<<n)-1];
	}
	for(int i=1;i<(1<<(n-1));i<<=1)for(int j=0;j<(1<<(n-1));j+=i<<1)
		for(int k=j;k<j+i;k++)ans[k]-=ans[k+i];
	Q=getint();
	while(Q--)
	{
		scanf("%s",s);int x=0;
		for(int i=0;i<n-1;i++)x=(x<<1)|(s[i]-48);
		printf("%lld
",ans[x]);
	}
}