Submission #19453963

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define popb pop_back
#define all(A) A.begin(),A.end()
#define rall(A) A.rbegin(),A.rend()
#define dic unordered_map
#define bpc __builtin_popcountll//numero de bits para long long
#define bclz __builtin_clzll//leading zeros para ll
#define max_bit(A) 31-__builtin_clz(A)
using namespace std;
const int maxn=1e5;
const ll mod=998244353;

int mid[maxn][5];
ll dp[maxn][2];

ll fpow(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	map<pair<int,int>,int> mp;
	vector<int> cnt(n,0);
	for(int i=3;i<n;i++) cnt[i]=i-2;
	for(int i=0;i<n;i++) for(int j=0;j<5;j++) mid[i][j]=-1;
	for(int i=0;i<m;i++){
		int a,b,c,d;
		cin>>a>>b>>c;
		a--,b--;
		d=max(a,b);
		if(max(a,b)-min(a,b)>2){
			mp[{a,b}]=c;
			if(mp.count({b,a})){
				if((mp[{a,b}]+mp[{b,a}])&1){
					cout<<"0\n";
					return 0;
				}
			} else cnt[d]--;
		}else{
			mid[d][a-b+2]=c;
		}
	}
	if(mid[0][2]==-1) dp[0][1]=dp[0][0]=1;
	else dp[0][mid[0][2]]=1,dp[0][mid[0][2]^1]=0;
	int libre=0,libre2;
	libre+=mid[1][1]==-1;
	libre+=mid[1][3]==-1;
	dp[1][0]=dp[1][1]=0;
	for(int i=0;i<2;i++){
		if(mid[1][2]==-1){
			for(int j=0;j<2;j++){
				if(libre){
					dp[1][j]+=dp[0][i]*fpow(2,libre-1);
				}else{
					if((i+j+mid[1][1]+mid[1][3])&1) continue;
					else dp[1][j]+=dp[0][i];
				}
			}
		}else{
			if(libre) dp[1][mid[1][2]]+=dp[0][i]*fpow(2,libre-1);
			else{
				if((i+mid[1][2]+mid[1][1]+mid[1][3])&1) continue;
				else dp[1][mid[1][2]]+=dp[0][i];
			}
		}
	}
	for(int k=2;k<n;k++){
		libre=0,libre2=0;
		libre+=mid[k][1]==-1;
		libre+=mid[k][3]==-1;
		libre2+=mid[k][0]==-1;
		libre2+=mid[k][4]==-1;
		dp[k][0]=dp[k][1]=0;
		for(int i=0;i<2;i++){
			if(mid[k][2]==-1){
				for(int j=0;j<2;j++){
					ll res;
					if(libre) res=(dp[k-1][i]*fpow(2,libre-1))%mod;
					else{
						if((i+j+mid[k][1]+mid[k][3])&1) continue;
						else res=dp[k-1][i];
					}
					if(libre2) res=(res*fpow(2,libre2-1))%mod;
					else if(((mid[k][0]+mid[k][4])&1)!=i) continue; 
					dp[k][i]=(dp[k][i]+res)%mod;
				}
			}else{
				ll res;
				if(libre) res=(dp[k-1][i]*fpow(2,libre-1))%mod;
				else{
					if((i+mid[k][2]+mid[k][1]+mid[k][3])&1) continue;
					else res=dp[k-1][i];
				}
				if(libre2) res=(res*fpow(2,libre2-1))%mod;
				else if(((mid[k][0]+mid[k][4])&1)!=i) continue;
				dp[k][mid[k][2]]=(dp[k][mid[k][2]]+res)%mod;
			}
		}
		ll e=fpow(2,cnt[k]);
		dp[k][0]=(dp[k][0]*e)%mod;
		dp[k][1]=(dp[k][1]*e)%mod;
	}
	//for(int i=0;i<n;i++) cout<<dp[i][0]<<" "<<dp[i][1]<<"\n";
	cout<<(dp[n-1][0]+dp[n-1][1])%mod<<"\n";
	// your code goes here
	return 0;
}

Submission Info

Judge Result