做那个网站大全/网页点击量统计

题目描述

第一行两个整数n, m。接下来m行，每行3个整数u, v, w，表示有一条边(u,v)，若w=-1则这条边上没有标记，否则w=0或1表示这条边上标记了w。数据保证没有重边和自环。1≤n≤100,000
0≤m≤min(n*(n-1)/2, 100000)

输出方案数对998,244,353取模的值。

题解：首先判断非法情况，也就是一个环上所有边都已经标记过了，并且所有的权值异或起来为1，此时我们可以考虑先将所有标记的边建成一张图，然后用类似于二染色的方法判断是否是非法情况。

对于合法情况，在一个环中根据边来找合法情况是困难的，于是我们要考虑如何将边权转化为点的权值，我们可以想到，假如当前一个环中所有的边都没有被标记，呢情况数是多少呢？

我们考虑这样一种做法（听室友讲，是一场区域赛题的解法），对于每个边的权值，将其转化为这条边的两个端点的异或值，因为这样做的话在一个环中每个点肯定异或两次！！！   是不是完美解决了上边的问题，呢答案不就是2^(3-1)=4了，为啥是3-1呢，你要知道对于当前的一种边权的状态，点权肯定有两种情况（所有点的权值取反即可）。。。

然后回到这道题，无非就是多了一些已经有标记的边，但是仔细想想会发现，这些已标记的边所在的联通块中的所有点权其实都是确定的。。。。想到这里答案就已经出来了。

呢最后答案无非就是2^（当前联通块大小）的乘积/（2^(已标记边的联通块大小)）

#include<vector>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll long long
#define mod 998244353
#define maxn 100005
ll ans=1;
int n,m,a[maxn],b[maxn],c[maxn],vis[maxn],flag[maxn],mark;
struct node
{int v,c;
};
vector<node>q[maxn];
ll qq(ll x,ll y)
{ll res=1;while(y){if(y%2)res=res*x%mod;x=x*x%mod;y/=2;}return res;
}
void dfs1(int x)
{if(mark) return;vis[x]=1;if(flag[x]==-1) flag[x]=1;for(int i=0;i<q[x].size();i++){int v=q[x][i].v;if(flag[v]==-1) flag[v]=(q[x][i].c^flag[x]);else {if((flag[x]^flag[v])!=q[x][i].c)mark=1;}if(vis[v]) continue;dfs1(v);}
}
ll dfs2(int x)
{ll tmp=0;vis[x]=1;for(int i=0;i<q[x].size();i++){int v=q[x][i].v;if(vis[v]) continue;tmp+=dfs2(v);}return tmp+1;
}
int main(void)
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&a[i],&b[i],&c[i]);if(c[i]!=-1){node tmp;tmp.v=b[i];tmp.c=c[i];q[a[i]].push_back(tmp);tmp.v=a[i];tmp.c=c[i];q[b[i]].push_back(tmp);}}memset(flag,-1,sizeof(flag));for(int i=1;i<=n;i++)if(!vis[i])dfs1(i);if(mark){printf("0\n");return 0;}for(int i=1;i<=m;i++){if(c[i]!=-1) continue;node tmp;tmp.v=b[i];tmp.c=c[i];q[a[i]].push_back(tmp);tmp.v=a[i];tmp.c=c[i];q[b[i]].push_back(tmp);}memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){if(vis[i]) continue;else{ll sum=dfs2(i);ans=(ans*qq(2ll,sum-1)%mod)%mod;}}for(int i=1;i<=n;i++)q[i].clear();for(int i=1;i<=m;i++){if(c[i]!=-1){node tmp;tmp.v=b[i];tmp.c=c[i];q[a[i]].push_back(tmp);tmp.v=a[i];tmp.c=c[i];q[b[i]].push_back(tmp);}}memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++){if(vis[i]) continue;else{ll sum=dfs2(i);ans=(ans*qq(qq(2,sum-1)%mod,mod-2)%mod)%mod;}}printf("%lld\n",ans);return 0;
}