自动搬运

查看原文

来自洛谷，原作者为

	nitrobenzene **

搬运于2025-08-24 22:03:09，当前版本为作者最后更新于2018-07-13 17:42:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻第一篇题解。。。 这道题，根据题意，此人会和所有好感度为正数的人结交。设有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;
}