题解 P4741 【[Wind Festival]Finding RhFe】

· · 题解

蒟蒻第一篇题解。。。 这道题，根据题意，此人会和所有好感度为正数的人结交。设有n人好感度为正数，而此人忘记好友的方式为后进先出，符合栈的特点，所以方式数为第n个卡塔兰数\frac{C_{2n}^n}{n+1}.

由于p不一定是质数，所以Lucas定理不能用，我们统计各个素因子在卡塔兰数中出现的幂次。注意到：在n！中，素因子p幂次为\sum_{i=1}^{+\infty}{[\frac{n}{p^i}]}.


 #include<set>////////
 #include<map>////////
 #include<cmath>//////
 #include<ctime>//////
 #include<queue>//////
 #include<stack>//////
 #include<cctype>///// 
 #include<cstdio>/////
 #include<vector>/////
 #include<string>/////
 #include<cstring>////
 #include<sstream>////
 #include<iostream>///
 #include<algorithm>//
using namespace std;//
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define ul unsigned long long
#define ll long long
const ll maxn=2001000;
bool vis[2001010];//是否是质数
vector<ll> p;//所有的质数
void init(){//筛质数
    ll n=maxn;
    memset(vis,1,sizeof(vis));
    vis[1]=0;
    vis[2]=1;
    p.push_back(2); 
    for(int i=4;i<=n;i+=2) vis[i]=0;
    for(ll i=3;i*i<=n;i+=2){
        if(vis[i]){

            for(ll j=i*i;j<=n;j+=i) vis[j]=0;
        }
    }
    for(int i=3;i<=maxn;i+=2){
        if(vis[i]) p.push_back(i); 
    }
    p.push_back(maxn); //防止后面过程中数组越界（反正最后2n是小于这个“质数”的，无影响）
}
int alpha[maxn]={0};//katalan数中各质数的幂次
void add_alpha_fact(int n){//阶乘素因子加成
    for(int i=0;p[i]<=n;i++){
        int res=n;
        while(res>0){
            res/=p[i];
            alpha[i]+=res;
        }
    }
}
void sub_twice_alpha_fact(int n){//阶乘素因子双倍减少
    for(int i=0;p[i]<=n;i++){
        int res=n;
        while(res>0){
            res/=p[i];
            alpha[i]-=(res+res);
        }
    }
}
void sub_alpha(int n){//单个数素因子减少
    for(int i=0;p[i]<=n;i++){
        while(n%p[i]==0){
            n/=p[i];
            alpha[i]--;
        }
    }
}
void katalan(int n){
    add_alpha_fact(2*n);//分子2n的阶乘
    sub_twice_alpha_fact(n);//分母n阶乘平方
    sub_alpha(n+1);//分母n+1
}
int main(){
    init();
    int cnt,cur,n=0;
    ll ha;
    cin>>cnt>>ha;
    while(cnt--){
        scanf("%d",&cur);
        if(cur>0) n++;
    }//统计好感度为正数的人数
    if(n==0){
        cout<<"TerriblePlace";
        return 0;
    }
    katalan(n);
    ll ans=1;
    rep(i,0,p.size() -1){
        while(alpha[i]--){
            ans=(ans*p[i])%ha;
        }
    }//乘起来
    cout<<ans;
    return 0;
}