听说3^n也能水过去。。
其实应该是个经典题，求图染色这个np问题。
把问题拆成独立集来进行dp可以在3^n之内水过去。
拆成独立集的时候就发现，等价与一个经典的反演dp问题
然后复杂度就变成了 n*n*2^n
另外，偷到一套头文件宏定义。
#include <math.h> #include <time.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <set> #include <map> #include <string> #include <stack> #include <queue> #include <vector> #include <bitset> #include <iostream> #include <algorithm> #define pb push_back #define fi first #define se second #define icc(x) (1<<(x)) #define lcc(x) (1ll<<(x)) #define lowbit(x) (x&-x) #define debug(x) cout<<#x<<"="<<x<<endl #define rep(i,s,t) for(int i=s;i<t;++i) #define per(i,s,t) for(int i=t-1;i>=s;--i) #define mset(g, x) memset(g, x, sizeof(g)) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef unsigned int ui; typedef double db; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> veci; const int mod=(int)1e9+7,inf=0x3fffffff,rx[]={-1,0,1,0},ry[]={0,1,0,-1}; const ll INF=1ll<<60; const db pi=acos(-1),eps=1e-8; template<class T> void rd(T &res){ res = 0; int ch,sign=0; while( (ch=getchar())!='-' && !(ch>='0'&&ch<='9')); if(ch == '-') sign = 1; else res = ch-'0'; while((ch=getchar())>='0'&&ch<='9') res = (res<<3)+(res<<1)+ch-'0'; res = sign?-res:res; } template<class T>void rec_pt(T x){ if(!x)return; rec_pt(x/10); putchar(x%10^48); } template<class T>void pt(T x){ if(x<0) putchar('-'),x=-x; if(!x)putchar('0'); else rec_pt(x); } template<class T>inline void ptn(T x){ pt(x),putchar(' '); } template<class T>inline void Max(T &a,T b){ if(b>a)a=b; } template<class T>inline void Min(T &a,T b){ if(b<a)a=b; } template<class T>inline T mgcd(T b,T d){ return b?mgcd(d%b,b):d; }//gcd模板，传入的参数必须是同一类型 //-------------------------------主代码--------------------------------------// int mat[20]; int mark[1<<18];//记录是否为独立集 int dp[20][1<<18]; int A[1<<18],B[1<<18]; int n; void gao(int _A[],int _B[],int C[]) { rep(i, 0, icc(n)){ A[i] = _A[i]; B[i] = _B[i]; } //传说中的or卷积 rep(i, 0, n){ rep(j, 0, icc(n)){ if( (icc(i)&j)){ A[j] += A[j^icc(i)]; B[j] += B[j^icc(i)]; } } } rep(i, 0, icc(n)) C[i] = A[i]*B[i]; //然后是逆着卷机 rep(i, 0, n){ rep(j, 0, icc(n)){ if( (icc(i)&j)){ C[j] -= C[j^icc(i)]; } } } } int main() { int T; rd(T); while(T--) { rd(n); rep(i, 0, n){ mat[i] = 0; rep(j, 0, n){ char tmp; cin>>tmp; if(tmp == '1') mat[i] |= icc(j); } } //mset(dp, 0); //然后求出独立集 mark[0] = 1; rep(i, 0, n){ rep(j, 0, icc(i)){ dp[1][icc(i)|j] = mark[icc(i)|j] = mark[j]==1?(mat[i]&j)==0:0; } } //然后开始dp rep(i, 1, n){ if(dp[i][icc(n)-1]) break;//这步优化很重要啊 gao(dp[i],mark,dp[i+1]); rep(j, 0, icc(n)) { dp[i+1][j] = (dp[i+1][j]!=0); //pt(dp[i+1][j]); putchar(' '); } //puts(""); } ui ans = 0; ui tmp = 1; rep(i, 1, icc(n)) { ui mj = 0; tmp *= 233; rep(j, 1, n+1){ if(dp[j][i]!=0){ mj = j; break; } } ans += mj*tmp; } ptn(ans); } return 0; } /* //-----------Test Case------------// */