【组合数学】EDU143 D. Triangle Coloring

╰半夏微凉° 2024-03-22 12:34 56阅读 0赞

**独立思考的时候想的思路和正解差不多！只不过缺点细节**

**感觉得多写写1600+的题，这样才能进步！**

[Problem - D - Codeforces][]

题意：

![9a35dacfde98435bb686530518c1651a.png][]

![7902839f93d4407abf7317e8dbfbad58.png][]

思路：

我自己想的时候的思路：

![66eaf397d7bc4b9eb3dfe4d8d852266e.jpeg][]

大差不差，但是缺了一种情况：等腰三角形的时候

果然是数学没学好了

总方案数=大方案数\*小方案数

Code：

#include <bits/stdc++.h>
    
    #define int long long 
    
    using namespace std;
    
    const int mxn=3e5+10; 
    const int mod=998244353;
    
    int N;
    int a[mxn],fac[mxn];
    
    int ksm(int a,int b,int mod){
    	int res=1ll;
    	while(b){
    		if(b&1) res=(res*a)%mod;
    		a=(a*a)%mod;
    		b>>=1;
    	}
    	return res;
    }
    int C(int n,int m){
    	return fac[n]*ksm(fac[m],mod-2,mod)%mod*ksm(fac[n-m],mod-2,mod)%mod;
    }
    void f_init(){
    	fac[0]=1;
    	for(int i=1;i<mxn;i++) fac[i]=(fac[i-1]*i)%mod;
    }
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	int sum=1;
    	for(int i=3;i<=N;i+=3){
    		if(a[i]==a[i-1]&&a[i-1]==a[i-2]) sum=(sum*3)%mod; 
    		else{
    			map<int,int> mp;
    			mp[a[i-2]]++,mp[a[i-1]]++,mp[a[i]]++;
    			if(mp[min(min(a[i-2],a[i-1]),a[i])]==2) sum=(sum*2)%mod;
    		}
    	}
    	cout<<C(N/3,N/6)*sum%mod<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	f_init();
    	while(__--)solve();return 0; 
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/1795/problem/D
[9a35dacfde98435bb686530518c1651a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/fea350ffc6e946f5be13aacb3be18905.png
[7902839f93d4407abf7317e8dbfbad58.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/0dda921dde584c99be700d93b4cf44b7.png
[66eaf397d7bc4b9eb3dfe4d8d852266e.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/d930da21d866451e9a8cda81bbf47d01.png