LOJ最优解达成！
题意
求满足下列要求的长度为 $2n$ 的序列 $S$ 的个数，对 $p$ 取模：
- 是 $2n$ 的全排列
- 奇数项、偶数项分别递增
- $\forall i\in [1,n] \ , \ S_{2i-1} < S_{2i}$
题解
对于性质 $2$ ，可以考虑将 $1...2n$ 的数字按照从小到大的顺序依次放入序列。每个数字可以放在最前的奇数或偶数位。
分析性质 $3$ ，显然偶数位上的数比它前面的所有数都大，也就是偶数位 $2i$ 上放的数满足 $S_{2i}\geq 2i$ 。继续分析感觉可以得到放在偶数位的个数应该 $\le$ 奇数位上的个数。
这就是卡特兰数的模型了，答案为 $\dfrac{C_{2n}^n}{n+1}$ 。
将上式转化
$$\dfrac{C_{2n}^n}{n+1} = \dfrac{(2n)!}{(n+1)!\times n!}$$
因为 $p$ 不是质数，没法直接用逆元，所以我直接把 $\text{exLucas}$ 改了一下就交了，然后很开心的得了 $90$ 。
然后发现那组数据的 $p$ 是个 $5e8$ 级别的质数，所以我对剩下的质数进行了特判，如果 $\geq 10^{6}$ 就直接用逆元算。
这种算法在LOJ拿了最优解，洛谷上在第二页，感觉复杂度还是比较优秀。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar();
ll f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
ll n,p,zs[20005],ans,cnt;
bool ss[100005];
inline void get_prime()
{
memset(ss,1,sizeof(ss));
ss[0]=ss[1]=0;
ll sqn=sqrt(p);
for (ll i=2;i<=sqn;i++)
{
if (ss[i]) zs[++cnt]=i;
for (ll j=1;j<=cnt && zs[j]*i<=sqn;j++)
{
ss[zs[j]*i]=0;
if (i%zs[j]==0) break;
}
}
}
ll exgcd(ll l,ll r,ll &x,ll &y)
{
if (r==0)
{
x=1; y=0;
return l;
}
ll ans=exgcd(r,l%r,y,x);
y-=l/r*x;
return ans;
}
inline ll qpow(ll x,ll y,ll ha)
{
ll ans=1;
while (y)
{
if (y&1) ans=ans*x%ha;
y>>=1;
x=x*x%ha;
}
return ans%ha;
}
inline ll inv(ll now,ll ha)
{
ll x=0,y=0;
exgcd(now,ha,x,y);
return (x%ha+ha)%ha;
}
inline ll fac(ll x,ll pi,ll pk)
{
if (!x) return 1;
ll ans=1;
for (ll i=2;i<=pk;i++)
{
if (i%pi==0) continue;
ans=ans*i%pk;
}
ans=qpow(ans,x/pk,pk);
ll len=x%pk;
for (ll i=2;i<=len;i++)
{
if (i%pi==0) continue;
ans=ans*i%pk;
}
return ans*fac(x/pi,pi,pk)%pk;
}
inline ll catalan(ll n,ll pi,ll pk)
{
ll s=0;
for (ll i=(n<<1);i;i/=pi) s+=i/pi;
for (ll i=n+1;i;i/=pi) s-=i/pi;
for (ll i=n;i;i/=pi) s-=i/pi;
return fac(n<<1,pi,pk)*inv(fac(n+1,pi,pk),pk)%pk*inv(fac(n,pi,pk),pk)%pk*qpow(pi,s,pk)%pk;
}
inline ll C(ll n,ll ha) //ha is prime
{
ll up=1,down=1;
for (ll i=n+2;i<=(n<<1);i++) up=up*i%ha;
for (ll i=n;i;i--) down=down*i%ha;
return up*inv(down,ha)%ha;
}
inline ll exlucas(ll n)
{
ll ans=0,p2=p;
for (ll i=1;i<=cnt;i++)
{
if (p2%zs[i]) continue;
ll pk=1;
while (p2%zs[i]==0) p2/=zs[i],pk*=zs[i];
ll ai=catalan(n,zs[i],pk),mi=p/pk;
ans=(ans+ai*mi%p*inv(mi,pk)%p)%p;
}
if (p2>1)
{
ll ai=(p2>1e6) ? C(n,p2) : catalan(n,p2,p2),mi=p/p2;
ans=(ans+ai*mi%p*inv(mi,p2)%p)%p;
}
return ans;
}
signed main()
{
n=read(); p=read();
get_prime();
return !printf("%lld",exlucas(n));
}