https://codeforces.com/problemset/problem/1093/D
思路:
开始看错题意,以为是赋值使得整个图的边权和为奇数,然后有多少种,想跑个背包肯定是tle的。
发现题目是求任意一边的两点权和为奇数。
那么1和3是等价的。单纯考虑1,然后3用组合数的办法解决。
间隔1和2可行,也就是二分图染色。
染出来的情况为101或者010.
对于101,每个1有两种可能,也就是2^(num1),对于010,其1的个数是原来图的补图,也就是sum-num1,同样这个1有两个可能.
综上就是2^(num1)+2^(sum-num1)
注意:只有一个点的时候是3个情况。存在不同连通块。答案在不同连通块之间是ans1*ans2...
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=3e5+100;
typedef long long LL;
LL mod=998244353;
inline LL read(){LL x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
vector<LL>g[maxn];
bool flag=1;
LL col[maxn];
LL num1=0,sum=0;///联通块的1的总数
LL ksm(LL a,LL k){LL res=1;while(k>0){if(k&1) res=res*a%mod;k>>=1;a=a*a%mod;}return res%mod;}
void dfs(LL u,LL num){
sum++;col[u]=num;
if(col[u]==1) num1++;
for(LL i=0;i<g[u].size();i++){
LL v=g[u][i];
if(col[v]==-1){
dfs(v,num^1);
}
else if(col[u]!=-1&&col[v]==col[u]){
flag=0;
return;
}
}
}
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
LL t;cin>>t;
while(t--){
LL n,m;cin>>n>>m;
for(LL i=0;i<n+10;i++) g[i].clear(),col[i]=-1,flag=1;
for(LL i=1;i<=m;i++){
LL u,v;cin>>u>>v;
g[u].push_back(v);g[v].push_back(u);
}
LL ans=1;
for(LL i=1;i<=n;i++){
if(col[i]==-1){
LL res=0;
num1=0;sum=0;
dfs(i,1);///先给第一个点染色为1
if(0==flag) break;
if(sum==1){
res=(res%mod+3%mod)%mod;
}
else res=(res%mod+ksm(2,num1)%mod+ksm(2,sum-num1)%mod)%mod;
ans=ans%mod*res%mod;
}
}
if(0==flag){
cout<<0<<"\n";
}
else{
cout<<ans%mod<<"\n";
}
}
return 0;
}