【UOJ#308】【UNR#2】UOJ拯救计划

题面

UOJ

题解

如果模数很奇怪，我们可以插值一下，设\(f[i]\)表示用了\(i\)种颜色的方案数。

然而模\(6\)这个东西很有意思，\(6=2*3\)，所以我们只需要考虑其模\(2\)和模\(3\)的结果了。

而最终答案的贡献是\(\sum_{i=1}^k A_{k}^i f[i]\)，当\(i\ge 3\)的时候\(6|A_k^i\)，所以我们只需要知道\(f[0],f[1],f[2]\)的值。

\(f[0]\)的值？当然是\(0\)啊。

\(f[1]\)的话，如果每个连通块都没有边的话就有方案数\(1\)，否则\(0\)。

\(f[2]\)的话，二分图染色，如果可以分成二分图，答案就是\(2\)的连通块个数次方

实际上因为只要\(m\neq 0\)，答案模\(2\)一定等于\(0\)，所以只需要考虑\(3\)的情况。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 100100

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,m,K;

int fpow(int a,int b){int s=1;while(b){if(b&1)s=s*a%6;a=a*a%6;b>>=1;}return s;}

vector<int> E[MAX];int col[MAX];bool fl;

void dfs(int u,int c)

{

	if(!fl)return;

	if(~col[u]){if(col[u]^c)fl=false;return;}

	col[u]=c;

	for(int v:E[u])dfs(v,c^1);

}

int main()

{

	int T=read();

	while(T--)

	{

		n=read();m=read();K=read();

		if(!m){printf("%d\n",fpow(K,n));continue;}

		for(int i=1;i<=m;++i)

		{

			int u=read(),v=read();

			E[u].push_back(v);

			E[v].push_back(u);

		}

		for(int i=1;i<=n;++i)col[i]=-1;

		fl=true;int cnt=0;

		for(int i=1;i<=n;++i)if(col[i]==-1)dfs(i,0),++cnt;

		if(!fl)puts("0");

		else printf("%d\n",K%6*(K-1)%6*fpow(2,cnt)%6*2%6);

		for(int i=1;i<=n;++i)E[i].clear();

	}

	return 0;

}