#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