Educational Codeforces Round 143 (Rated for Div. 2) D - Triangle Coloring

lucas定理求大组合数取模板子

#include<bits/stdc++.h>
#define fi first
#define se second
#define io std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const ll mod=998244353,INF = 0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll exgcd(ll a, ll b, ll &x, ll &y) {if(!b) {x = 1; y = 0; return a;}ll r = exgcd(b, a % b, x, y);ll tmp = x; x = y, y = tmp - a / b * y;return r;}
ll qpow(ll a,ll n){ll r=1;for (; n; a=a*a,n>>=1)if(n&1)r=r*a;return r;}
ll qpow(ll a,ll n,ll P){ll r=1%P;for (a%=P; n; a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
string getbinarystring(ll x){if(x==0) return string("0");string res;while(x){if(x&1) {res.push_back('1');}else {res.push_back('0');}x>>=1;}reverse(res.begin(),res.end());return res;}


const int maxn=3e5+10;



ll C(ll n,ll m,ll p,vector<ll> &a){
    if(m>n)return 0;
    return ((a[n]*qpow(a[m],p-2,p))%p*qpow(a[n-m],p-2,p)%p);
}
ll Lucas(ll n, ll m,ll p,vector<ll> &a) {
  if (m == 0) return 1;
  return (C(n % p, m % p,p,a) * Lucas(n / p, m / p,p,a)) % p;
}
ll Lucas_solve(ll n,ll m,ll p)   //模数必须为质数，否则用扩展lucas
{        
       vector<ll> a;
       a.resize(n+1);   //存阶乘
       a[0]=1;
       for(int i=1;i<=n;i++)a[i]=(a[i-1]*i)%p;
       return Lucas(n,m,p,a);
}




int main()
{

      
  

int n;
cin>>n;
    n=n/3;
    ll w=Lucas_solve(n,n/2,mod);
ll ans=1;
    for(int i=1;i<=n;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;


        if(x==y&&x==z)
            ans*=3;
        else if(x==y&&z>y)
            ans*=2;
        else if(x==z&&y>z)
            ans*=2;
        else if(z==y&&x>z)
            ans*=2;

        ans%=mod;
    }
    cout<<ans*w%mod<<endl;
  
}