D. Beautiful Graph(思维+二分图染色)

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;
}

 

上一篇:Codeforces Round #705 (Div. 2) C. K-beautiful Strings(思维 枚举)


下一篇:[转载] Python中三种类型的引号(单引号、双引号、三引号)