一个图的 k 染 {MOD}数是关于 k 的 n 次(?) 多项式
称为 {MOD}多项式
那么这里模6 我们只要知道模2和模3的值
然后分类讨论下就好了
一张图的0染 {MOD}数是0，1染 {MOD}数等于[m=0]，2染 {MOD}数与二分图的联通块个数有关 #include #include #include #include #define cl(x) memset(x,0,sizeof(x)) using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int N=100005; struct edge{ int u,v,next; }G[N<<2]; int head[N],inum; inline void add(int u,int v,int p){ G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p; } #define V G[p].v int fat[N],depth[N]; int flag=0; inline void dfs(int u,int fa){ fat[u]=fa; depth[u]=depth[fa]+1; for (int p=head[u];p;p=G[p].next) if (V!=fa){ if (!depth[V]){ dfs(V,u); }else if (depth[V]%2==0); } } } int n,m,K; inline int Pow(int a,int b,int P){ int ret=1; for (;b;b>>=1,a=a*a%P) if (b&1) ret=ret*a%P; return ret; } int main(){ int T,x,y; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(T); while (T--){ read(n); read(m); read(K); inum=0; cl(head); for (int i=1;i<=m;i++) read(x),read(y),add(x,y,++inum),add(y,x,++inum); int mod2,mod3; if (~K&1) mod2=0; else mod2=(m==0); if (K%3==0) mod3=0; else if (K%3==1) mod3=(m==0); else{ cl(depth); cl(fat); int cnt=0; flag=0; for (int i=1;i<=n;i++) if (!depth[i]) cnt++,dfs(i,0); if (flag) mod3=0; else mod3=Pow(2,cnt,3); } for (int i=0;i<6;i++) if (i%2==mod2 && i%3==mod3) printf("%d ",i); } return 0; } TC那个题是求把无向图定向成DAG的方案数
有定理，也可见这里

The number of Acyclic Orientations of an undirected graph is given by ( − 1)N⋅P(−1), where P is the chromatic polynomial of the given graph.

// BEGIN CUT HERE #include #include // END CUT HERE #include #include #include #include #include #include #include #include #include #include #define cl(x) memset(x,0,sizeof(x)) using namespace std; typedef long long ll; const int N=105; const int M=N*N; struct edge{ int u,v,next; }G[M]; int head[N],inum; inline void add(int u,int v,int p){ G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p; } #define V G[p].v int depth[N]; int flag=0; inline void dfs(int u,int fa){ depth[u]=depth[fa]+1; for (int p=head[u];p;p=G[p].next) if (!depth[V]) dfs(V,u); else if (depth[V]2==0) flag=1; } inline int Pow(int a,int b){ int ret=1; for (;b;b>>=1,a=a*a%3) if (b&1) ret=ret*a%3; return ret; } class AcyclicOrientation{ public: int count(int n, vector <int> u, vector <int> v){ cl(head); inum=0; cl(depth); flag=0; for (int i=0;i<(int)u.size();i++) add(u[i]+1,v[i]+1,++inum),add(v[i]+1,u[i]+1,++inum); int m2=(u.size()==0),m3,C=0; for (int i=1;i<=n;i++) if (!depth[i]) dfs(i,0),C++; if (flag) m3=0; else m3=Pow(2,n+C); for (int i=0;i<6;i++) if (i%2==m2 && i%3==m3) return i; } // BEGIN CUT HERE public: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); } private: template <typename T> string print_array(const vector &_V) { ostringstream os; os << "{ "; for (typename vector::const_iterator iter = _V.begin(); iter != _V.end(); ++iter) os << '"' << *iter << "","; os << " }"; return os.str(); } void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << " Expected: "" << Expected << '"' << endl; cerr << " Received: "" << Received << '"' << endl; } } void test_case_0() { int Arg0 = 3; int Arr1[] = {0, 1, 0}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {2, 2, 1}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 0; verify_case(0, Arg3, count(Arg0, Arg1, Arg2)); } void test_case_1() { int Arg0 = 5; int Arr1[] = {0, 1, 2, 3}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {1, 2, 3, 4}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 4; verify_case(1, Arg3, count(Arg0, Arg1, Arg2)); } void test_case_2() { int Arg0 = 4; int Arr1[] = {0, 3}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {1, 1}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arg3 = 4; verify_case(2, Arg3, count(Arg0, Arg1, Arg2)); } // END CUT HERE }; // BEGIN CUT HERE int main(){ AcyclicOrientation ___test; ___test.run_test(-1); getch() ; return 0; } // END CUT HERE