自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:30:21，当前版本为作者最后更新于2021-03-20 13:57:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

找规律结论题。答案为 $Q_n^m=C_n^m \times A_n^m$。直接推几项，大力猜结论。可以用数学归纳法证明如下：

设 $\forall i \le n,j \le i,Q_i^j=C_i^j \times A_i^j,$

分第 $i+1$ 只白色蜻蜓是否在 $j$ 只当中讨论（其实就是考虑 dp）得

$$\begin{aligned} Q_{i+1}^j&=Q_i^j+Q_i^{j-1} \times (2i-j+2)\\ &=C_i^jA_i^j+(2i-j+2)C_i^{j-1}A_i^{j-1}\\ &=\frac{(i!)^2}{j![(i-j)!]^2}+\frac{(i!)^2(2i-j+2)}{(j-1)![(i-j+1)!]^2}\\ &=\frac{(i!)^2[(i-j+1)^2+(2i-j+2)j]}{j![(i-j+1)!]^2}\\ &=\frac{[(i+1)!]^2}{j![(i+1-j)!]^2}\\ &=C_{i+1}^jA_{i+1}^j. \end{aligned}$$

$p$ 不一定是质数，直接上 exLucas。注意 $m \ge p$ 时答案是 $p$ 的倍数，所以事实上只用做 $n,m$ 很小的情况。

时间复杂度 $O(p\log{p})$。

Code:

#include<map>
#include<list>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
LL n,m,p,ans;
inline LL exgcd(LL a,LL b,LL &x,LL &y)
{
	if(!b)
	{
		x=1;y=0;
		return a;
	}
	LL r=exgcd(b,a%b,y,x);
	y-=(a/b)*x;
	return r;
}
inline LL mul(LL a,LL b,LL n)
{
	return a*b%n;
}
inline LL qpw(LL n,LL k,LL m)
{
	LL res=1;
	while(k)
	{
		if(k&1)res=mul(res,n,m);
		n=mul(n,n,m);
		k>>=1;
	}
	return res;
}
inline LL fac(LL n,LL pi,LL pk)
{
	if(!n)return 1;
	LL res=1;
	for(LL i=2;i<=pk;++i)
	{
		if(i%pi)res=mul(res,i,pk);
	}
	res=qpw(res,n/pk,pk);
	for(LL i=2;i<=n%pk;++i)
	{
		if(i%pi)res=mul(res,i,pk);
	}
	return mul(res,fac(n/pi,pi,pk),pk);
}
inline LL inv(LL n,LL m)
{
	LL x,y;
	exgcd(n,m,x,y);
	return (x+m)%m;
}
inline LL crt(LL b,LL m)
{
	return mul(mul(b,inv(p/m,m),p),p/m,p);
}
inline LL C(LL n,LL m,LL pi,LL pk)
{
    LL so=fac(n,pi,pk),fa=fac(m,pi,pk),mo=fac(n-m,pi,pk);
    LL k=0;
    for(LL i=n;i;i/=pi)k+=i/pi;
    for(LL i=m;i;i/=pi)k-=i/pi;
    for(LL i=n-m;i;i/=pi)k-=i/pi;
    return mul(mul(mul(so,inv(fa,pk),pk),inv(mo,pk),pk),qpw(pi,k,pk),pk);
}
inline LL exlucas(LL n,LL m)
{
	LL res=0,k=p,pk;
	LL maxx=sqrt(p)+6;
	for(LL i=2;i<maxx;++i)
	{
		if(k%i)continue;
		pk=1;while(k%i==0)pk*=i,k/=i;
		res=(res+crt(C(n,m,i,pk),pk))%p;
	}
	if(k>1)res=(res+crt(C(n,m,k,k),k))%p;
	return res;
}
int main()
{
    scanf(" %lld %lld %lld",&n,&m,&p);
    if(m>=p)return 0&puts("0");
    ans=exlucas(n,m);
    ans=ans*ans%p;
    for(int i=1;i<=m;++i)ans=ans*i%p;
    printf("%lld\n",ans);
    return 0;
}