C++ 解法, 执行用时: 898ms, 内存消耗: 250872K, 提交时间: 2021-09-01 02:56:33

#include<bits/stdc++.h> 
using namespace std;
long long n,mod,cnt=0,c[1000005][30],fac[1000005],inv[1000005],f[30];
long long qsm(long long a,long long b){
	long long ret=1; while(b) { if(b&1) ret*=a,ret%=mod; b>>=1,a*=a,a%=mod; } return ret;
}
void init(){
	fac[0]=inv[0]=1; long long t=mod,phi=mod;
	for(int i=2;i*i<=t;i++) if(t%i==0) { f[cnt++]=i,phi/=i,phi*=i-1; while(t%i==0) t/=i; }
	if(t>1) f[cnt++]=t,phi/=t,phi*=t-1; phi--;
	for(int i=1;i<=n;i++){
		long long x=i;
		for(int j=0;j<cnt;j++){
			c[i][j]=c[i-1][j];
			while(x%f[j]==0) x/=f[j],c[i][j]++;
		}
		fac[i]=fac[i-1]*x%mod,inv[i]=qsm(fac[i],phi);
	}
}
long long C(long long n,long long m){
	if(n<m) return 0; if(m==0) return 1; long long ret=fac[n]*inv[m]%mod*inv[n-m]%mod;
	for(int i=0;i<cnt;i++) ret*=qsm(f[i],c[n][i]-c[m][i]-c[n-m][i]),ret%=mod;
	return ret;
}
int main(){
	cin >> n >> mod;init();long long ans=1,ed=n/2;
	for(int i=1;i<=ed;i++) ans+=C(2*i,i)*C(n,2*i)%mod,ans-=ans>=mod?mod:0; cout << ans; 
}