官方题解 | Run

F. Run

Subtask 10 pt

对于 $10\%$ 的数据 $n \le 5\times 10^3$，直接代入公式暴力递推、枚举即可。

Subtask 40 pt

首先化简公式，引入杨辉三角（当然使用 Catalan 数亦可）：

$$1\\ 1\ 1\\ 1\ 2\ 1\\ 1\ 3\ 3\ 1\\ \ldots$$

杨辉三角的实质是二项式系数的几何排列。若一个人从第一个 $1$ 处走，只能向下或右下，走到该地的方案数。其组合数表示为：

$$C_n^k=\frac{n!}{k!\times(n-k)!}$$

容易将公式转换为：

$$\sum_{k=0}^n(_k^n)^2\bmod p$$

根据范德蒙德公式化简：

$$\sum_{k=0}^n(_k^n)^2\bmod p\\ =\sum_{k=0}^n(_{n-k}^{n})(_k^n)\bmod p\\$$

再根据二项式定理化简：

$$\sum_{k=0}^n(_{n-k}^{n})(_k^n)\bmod p\\ =(_n^{2n})\bmod p$$

拓展：实际上存在 Vandermonde 恒等式可直接得到：

$$\sum_{k=0}^n(_k^n)^2=(_n^{2n})$$

两边同时 $\bmod p$，得：

$$\sum_{k=0}^n(_k^n)^2 \bmod p=(_n^{2n})\bmod p$$

由于 $p \in \operatorname{Prime}$，考虑使用 Lucas 定理：

$$(_n^k)\equiv(_{\lfloor k/p \rfloor}^{\lfloor n/p \rfloor})(_{k \bmod p}^{n \bmod p})\pmod p$$

其中，当 $n<k$ 时，二项式系数 $(_n^k)$ 规定为 $0$​。

递归求解即可。

40 pt Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int fp(int a,int b,int p){
	int ans = 1;
	while(b){
		if(b & 1) ans = ans * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return ans;
}
int ans[10000005];
int C(int n,int m,int p){
    ans[0] = 1;
	for(int i = 1;i <= m;i++){
        ans[i] = 0;
        ans[i] = ans[i - 1] * (n - i + 1) % p * fp(i,p - 2,p) % p;
    }
	return ans[m];
}
int lucas(int n,int m,int p){
	if(m == 0) return 1;
	return lucas(n / p,m / p,p) * C(n % p,m % p,p) % p;
}
signed main(){
    int n,p; cin >> n >> p;
    cout << lucas(n * 2,n,p);
    return 0;
}

时间复杂度：$O(p+\log_p n)$

Subtask 100 pt

请先阅读 40 pt 做法。

由于 Lucas 定理只能在 $p$ 为质数的情况下使用，对于 $100\%$ 的数据我们考虑扩展 Lucas 定理。

对于 $p$ 是一般的合数的情形，只需要首先对它做素因数分解：

$$p=m_1^{a_1}m_2^{a_2}\ldots m_s^{a_s}$$

然后，分别计算出模 $m_i^{a_i}$ 下组合数 $(_k^n)$ 的余数，就得到 $s$ 个同余方程：

$$\begin{equation} \begin{cases} (_k^n)\equiv r_1\pmod{p_1^{a_1}}\\ (_k^n)\equiv r_2\pmod{p_2^{a_2}}\\ \ldots\\ (_k^n)\equiv r_s\pmod{p_s^{a_s}} \end{cases} \end{equation}$$

引入中国剩余定理（CRT）：

$$\begin{equation} \begin{cases} x\equiv a_1\pmod{n_1}\\ x\equiv a_2\pmod{n_2}\\ \ldots\\ x\equiv a_k\pmod{n_k} \end{cases} \end{equation}$$

利用中国剩余定理（CRT）即可求出模 $p$ 的余数。

AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#ifndef Fading
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
#endif
#ifdef Fading
#define gc getchar
#endif
void exgcd(ll a,ll b,ll &x,ll &y){
    if (!b) return (void)(x=1,y=0);
    exgcd(b,a%b,x,y);
    ll tmp=x;x=y;y=tmp-a/b*y;
}
ll gcd(ll a,ll b){
    if (b==0) return a;
    return gcd(b,a%b); 
}
inline ll INV(ll a,ll p){
    ll x,y;
    exgcd(a,p,x,y);
    return (x+p)%p;
}
inline ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
inline ll mabs(ll x){
    return (x>0?x:-x);
}
inline ll fast_mul(ll a,ll b,ll p){
    ll t=0;a%=p;b%=p;
    while (b){
        if (b&1LL) t=(t+a)%p;
        b>>=1LL;a=(a+a)%p;
    }
    return t;
}
inline ll fast_pow(ll a,ll b,ll p){
    ll t=1;a%=p;
    while (b){
        if (b&1LL) t=(t*a)%p;
        b>>=1LL;a=(a*a)%p;
    }
    return t;
}
inline ll read(){
    ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();}
    while (isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x*f;
}
inline ll F(ll n,ll P,ll PK){
    if (n==0) return 1;
    ll rou=1;
    ll rem=1;
    for (ll i=1;i<=PK;i++){
        if (i%P) rou=rou*i%PK;
    }
    rou=fast_pow(rou,n/PK,PK);
    for (ll i=PK*(n/PK);i<=n;i++){
        if (i%P) rem=rem*(i%PK)%PK;
    }
    return F(n/P,P,PK)*rou%PK*rem%PK;
}
inline ll G(ll n,ll P){
    if (n<P) return 0;
    return G(n/P,P)+(n/P);
}
inline ll C_PK(ll n,ll m,ll P,ll PK){
    ll fz=F(n,P,PK),fm1=INV(F(m,P,PK),PK),fm2=INV(F(n-m,P,PK),PK);
    ll mi=fast_pow(P,G(n,P)-G(m,P)-G(n-m,P),PK);
    return fz*fm1%PK*fm2%PK*mi%PK;
}
ll A[1001],B[1001];
//x=B(mod A)
inline ll exLucas(ll n,ll m,ll P){
    ll ljc=P,tot=0;
    for (ll tmp=2;tmp*tmp<=P;tmp++){
        if (!(ljc%tmp)){
            ll PK=1;
            while (!(ljc%tmp)){
                PK*=tmp;ljc/=tmp;
            }
            A[++tot]=PK;B[tot]=C_PK(n,m,tmp,PK);
        }
    }
    if (ljc!=1){
        A[++tot]=ljc;B[tot]=C_PK(n,m,ljc,ljc);
    }
    ll ans=0;
    for (ll i=1;i<=tot;i++){
        ll M=P/A[i],T=INV(M,A[i]);
        ans=(ans+B[i]*M%P*T%P)%P;
    }
    return ans;
}
signed main(){
    int n,p; cin >> n >> p;
    cout << exLucas(n * 2,n,p);
}

时间复杂度：$O(\log n)$