【UOJ#308】【UNR#2】UOJ拯救计划
2024-10-07 02:48:21
【UOJ#308】【UNR#2】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;
}
最新文章
- 一些值得练习的github项目
- java基于socket的简单聊天系统
- HTML 表单和输入<;form>;<;input>;
- nodejs学习资料
- 【转】Image Cyborg 一键下载存储网页所有图片
- 动态调用WebService 通用方法Moss 中 传统开发中都可用。
- 简洁 Abstract Factory模式(3.1)
- 【转】HttpServlet详解
- tornado.web.Application类配置及使用
- 求1~n直接1出现的次数
- 【English】十五、“a”和“one”的区别是什么?
- mssql sqlserver with cte表达式(递归)找出最顶值的方法分享
- 1019. General Palindromic Number (20)
- 云数据库POLARDB优势解读之①——10分钟了解
- c++多继承布局
- Player Settings 导出设置
- 将句子表示为向量(上):无监督句子表示学习(sentence embedding)
- 【learning】 单调队列与单调栈用法详解
- (二) Mysql 数据类型简介
- SQLServer 2005 和自增长主键identity说再见——NEWSEQUENTIALID()
热门文章
- Newtonsoft.Json 指定某个属性使用特定的时间格式
- python爬取网站视频保存到本地
- 敏捷软件开发_UML<;一>;
- 【LeetCode】650. 只有两个键的键盘
- JDK8日常开发系列:Consumer详解
- PHP代码篇(二)-- array_column函数将二维数组格式化成固定格式的一维数组,及优化查询方法
- bayaim_java_入门到精通_听课笔记bayaim_20181120
- Mysql添加用户与授权
- 【cf570】D. Tree Requests(dsu on tree)
- java中的字符串二