题目背景

我的母亲柯蒂丽亚,是一个舞者。身披罗纱,一身异国装扮的她,来自灰狼的村子。

曾经在灰狼村子担任女侍的她,被认定在某晚犯下可怕的罪行之后,被赶出了村子。

一切的元凶,都要回到母亲犯下重罪的那一晚。

题目描述

我不认为柯蒂丽亚有犯罪。

二十年前的混沌,一共有n块碎片。

这n块碎片曾经两两之间都有联系,可是很多联系都在时间的洪流中消失了。

现在,我只能确定其中m条联系的种类。

每条联系都是一条无向边,任意两块碎片之间至多有一条联系,没有联系会连接在同一块碎片的两端。

联系有两种。一种是冲突,用0表示;另一种是吻合,用1表示。

虽然已经过去了二十年,但是联系的种类是不会变的。

现在,我想要用这m条联系,去推断二十年前的n(n-1)/2条联系的种类。

如果我推理出所有联系的种类,那么我就可以将混沌言语化,证明柯蒂丽亚的清白。

在灰狼的村子,我得知了推理的唯一条件:

二十年前,对于任意三块互不相同的碎片,要么这三块碎片两两吻合,要么恰好有一对碎片互相吻合。

我想要知道,二十年前n块碎片两两之间的联系,可能有多少种。

你只要输出方案数模998244353之后的结果。如果已经确定的m条联系不符合上述条件,请输出0。

两种方案不同,当且仅当存在两块碎片,在一种方案中冲突,在另一种方案中吻合。也就是说,你要求的是有多少种可能的原图。

【输入描述】

第一行两个整数Test,T,Test表示测试点的编号,T表示数据的组数。保证T≤3。

接下来T组数据,每组数据第一行两个整数n,m,

接下来m行,每行三个整数u,v,t,表示第u块碎片和第v块碎片之间联系的种类为t。

【输出描述】

共T行,每行一个整数,表示方案数对998244353取模后的结果。

输入输出格式

输入格式:

输出格式:

输入输出样例

输入样例#1:

0 2
3 0
4 2
1 2 1
1 3 0
输出样例#1:

4
2

说明

n <= 10^5

m <= 10^6

分析:考虑这样一个图:常州模拟赛d3t2 灰狼呼唤着同胞-LMLPHP,把一个连通块分成AB两部分,其中A和B两个不同的集合中每两个点都是吻合的,A集合的点到B集合的点之间每两个点都是冲突的.这样你任取三个点都是满足要求的.然后我们新加一个连通块:常州模拟赛d3t2 灰狼呼唤着同胞-LMLPHP,连线的代表都是冲突的,圆圈里的是吻合的,这是一种合法的方案,我们把CD交换一下,得到的又是一种新的方案,然后这两个连通块又可以合并成一个连通块.n个连通块有2*(n-1)条边连接,每两条边可以互换,这也就是说答案就是2^(cnt - 1),cnt为连通块个数。如果连通块退化成一个点也成立.

关于如何求连通块个数:有向图可以用tarjan缩点,无向图可以用并查集.

考场上犯了几个脑残错误:1.flag没有清零 2.快速幂传递的参数传成了int,大数据直接爆掉QAQ,结果只有10分.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath> using namespace std; const int mod = ; int test, t, n, m, fa[];
bool flag = false; int find(int x)
{
if (x == fa[x])
return x;
return fa[x] = find(fa[x]);
} void hebing(int x, int y)
{
int fx = find(x), fy = find(y);
if (fx != fy)
fa[fy] = fx;
} long long qpow(long long a, long long n)
{
long long result = ;
while (n) {
if (n & ) result = (result*a) % mod;
a = (a*a) % mod;
n >>= ;
}
return result;
} int main()
{
scanf("%d%d", &test, &t);
while (t--)
{
flag = ;
scanf("%d%d", &n, &m);
for (int i = ; i <= * n; i++)
fa[i] = i;
for (int i = ; i <= m; i++)
{
int u, v, tt;
scanf("%d%d%d", &u, &v, &tt);
if (tt == )
{
if (find(u + n) == find(v) || find(u) == find(v + n))
flag = ;
else
{
hebing(u, v);
hebing(u + n, v + n);
}
}
else
{
if (find(u) == find(v) || find(u + n) == find(v + n))
flag = ;
else
{
hebing(u + n, v);
hebing(u, v + n);
}
}
}
if (flag)
printf("0\n");
else
{
int cnt = ;
for (int i = ; i <= n; i++)
if (fa[i] == i)
cnt++;
printf("%lld\n", qpow(, cnt - ));
}
} return ;
}
05-11 15:25