首页 > 其他分享 >D. Triangle Coloring (组合数)

D. Triangle Coloring (组合数)

时间:2023-02-17 15:33:30浏览次数:37  
标签:Coloring Triangle ifac 组合 int res ll long mod

#pragma GCC optimize ("O3")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("O1")
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
const ull base1 = 131;
const ull base2 = 13331;
const ll N = 3e5 + 5, M = 9e18 ;
#define PI 3.141592653589793
ll mod=998244353LL,mod2=1000000007;
using namespace std;
//组合数板子
ll fac[N], ifac[N];
ll qmi(ll a,ll k,ll p)
{
    ll res=1;
    while(k){
        if (k&1) res=(res*a)%p;
        a=(a*a)%p;
        k>>=1;
    }
    return res%mod;
}
void init(){
    fac[0]=ifac[0]=1LL;
    for (ll i=1;i<N;i++){
        fac[i]=(fac[i-1]*i)%mod;
        ifac[i]=(ifac[i-1]*qmi(i,mod-2,mod))%mod;
    }
}
ll C(ll n,ll m){
    if(m>n) return 0;
    return ((fac[n]*ifac[m])%mod*ifac[n-m])%mod;
}
//组合数板子
void solve(){
    int n;cin>>n;
    vector<ll> a(n+3);
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    ll ans=1;
    for(int i=1;i<=n;i+=3){
        sort(a.begin()+i,a.begin()+i+3);
        if(a[i]==a[i+1]&&a[i+1]==a[i+2]) ans*=3;
        else if(a[i]==a[i+1]) ans*=2;
        ans%=mod;
    }
    ans*=C(n/3,n/6);ans%=mod;
    cout<<ans<<"\n";
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);std::cout.tie(0);
    init();
    solve();
}

只需要分类三元组内能达到最大值的两条边的数量,最后乘上C(n/3,n/6)即可

标签:Coloring,Triangle,ifac,组合,int,res,ll,long,mod
From: https://www.cnblogs.com/zesure-blog/p/17130349.html

相关文章