C++(g++ 7.5.0) 解法, 执行用时: 28ms, 内存消耗: 2896K, 提交时间: 2022-08-10 16:14:15

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 2000010;
int primes[N], cnt;
bool st[N];

int n, mod;

void init(int n) {
    for (int i = 2; i <= n; i++) {
        if(!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int qmi(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod) {
        if(b & 1) res = 1ll * res * a % mod;
    }
    return res;
}

int get(int n, int p) {
    int s = 0;
    for (; n; n /= p) s += n / p;
    return s;
}

int C(int a, int b) {
    int res = 1;
    for (int i = 0; i < cnt; i++) {
        int p = primes[i];
        int s = get(a, p) - get(b, p) - get(a - b, p);
        res = 1ll * res * qmi(p, s) % mod;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> mod;
    init(2 * n);

    cout << (C(2 * n, n) - C(2 * n, n - 1) + mod) % mod;

    return 0;
}

C++ 解法, 执行用时: 65ms, 内存消耗: 32752K, 提交时间: 2022-04-06 11:00:50

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll prime[2000005],a[2000005],come[2000005];
ll ans=1,n,p,cnt,mod;
ll fpow(ll a,ll b)
{
	ll ans;
	for(ans=1;b;b=b/2,a=a*a%mod)
	if(b&1)
	ans=ans*a%mod;
	return ans;
}
int main()
{
	cin>>n>>mod;
	for(ll i=2;i<=n*2;i++) {
		if(!come[i])
		prime[++cnt]=i;
		for(ll j=1;j<=cnt&&prime[j]*i<=n*2;j++)
		come[prime[j]*i]=i;
	}
	for(ll i=2;i<=n;i++)a[i]=-1;
	for(ll i=n+2;i<=2*n;i++)a[i]=1;
	for(ll i=n*2;i>1;i--)
	if(come[i]) {
		a[come[i]]+=a[i];
		a[i/come[i]]+=a[i];
	}
	else ans=ans*fpow(i,a[i])%mod;
	cout<<ans;
	return  0;
}