D. Triangle Coloring

https://codeforces.com/contest/1795/problem/D
#include <iostream>

#include <cstring>

#include <algorithm>

#include <string>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=3e5+10,mod=998244353;

int n;

ll qmi(ll a,ll k){

	ll res=1;

	while(k){

		if(k&1) res=res*a%mod;

		k>>=1;

		a=a*a%mod;

	}

	return res;

}

bool fact(int a,int b,int c){

	return a==b&&a<c&&b<c;

}

int main(){

		ll res=1;

		cin>>n;

		ll k=1;

		for(int i=1;i<=n;i+=3){

			int x,y,z;

			cin>>x>>y>>z;

			if(x==y&&x==z) k=k*3%mod;

			else if(fact(x,y,z)||fact(x,z,y)||fact(y,z,x)) k=k*2%mod;

		}

		for(int i=n/3,j=1;i>n/6;i--,j++){

			res=res*i%mod;

			res=res*qmi(j,mod-2)%mod;

		}

		res=res*k%mod;

		cout<<res<<endl;

}

/*

就是每三个点一组，给所有数字染色，颜色只有红蓝，且一半染红一半染蓝

要想要使得结果最大

每个三原组有两种染法，红蓝蓝或者蓝红红

我们一共n/3个组，根据对称可得，n/6个得染红蓝蓝

另外有些特殊情况

例如当三个边权都一样时，就有三种情况

当两个边权一样且都是小边权时有两种情况

*/
巴特西

D. Triangle Coloring

最新文章

热门文章
