D 黑色毛衣 题解
VinstaG173
·
·
题解
找规律结论题。答案为 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）得
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}
时间复杂度 $O(p\log{p})$。
Code:
```cpp
#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;
}
```