描述 Description
You are given a function f which is defined as :
\[ f(N)=1^1*2^2*3^2*...*(N-1)^{N-1}*N^N \]
Your task is to find the value of \(\frac{f(N)}{f(r)*f(N-r)}\). As it will be a large number output it modulo \(M\).
输入格式 InputFormat
First line contains T , number of test cases to follow.
Next follows T test case.
First line of ever test case contain 3 space separated integers N , M and Q.
Next Q line follows , each line contain r.
输出格式 OutputFormat
For every test case , output Q lines , each line containing the answer.
样例输入 SampleInput
1
5 24 2
2
3
样例输出 SampleOutput
8
8
因为 \(f(r)\) 和 \(f(N-r)\) 有可能不是与 \(M\) 互质，所以不能直接用逆元来做。那么我们先提出 \(f(r)\) 和 \(f(N-r)\) 中含有的 \(M\) 的质因子用 \(g[]\) 表示，用逆元算出初始答案，再乘上这些质因子。
\(a\) 在模 \(m\) 意义下的乘法逆元为 \(a^{\phi(m)-1} \ mod \ m\)。
用 \(x_i,y_i,z_i\) 表示分别使 \(p_{i}^{x_i},p_{i}^{y_i},p_{i}^{z_i}\) 为 \(f[n],f[r],f[n-r]\) 的因数时最大的指数。
于是最终答案为 \[ g[n]*g[r]^{\phi(m)-1}*g[n-r]^{\phi(m)-1}*\prod_{i=1}^{p_i \in Frac(m)}p_i^{x_i-y_i-z_i} \]
重点是如何去计算这个 \(x_i,y_i,z_i\)，我们要满足的条件是 \(f(i) \ mod \ p_i^x=0\) 时 \(x\) 取最大值。
这里我们假定 \(i=9,p_i=2\) 来推一下计算方法，即寻找满足 \(\prod_{i=1}^{9}i^i \ mod \ 2^x=0\) 的 \(x\) 的最大值。
可知为了使模等于零，答案只与 \(f(i)\) 中 \(2\) 的倍数有关系，即 \(2^2*4^4*6^6*8^8 \ mod \ 2^x=0\).
分解提取得 \((2^2)*(2^4*2^4)*(2^6)*(2^8*2^8*2^8) \ mod \ 2^x=0\) \[ \Rightarrow (2^2*2^4*2^6*2^8)*(2^4*2^8)*(2^8) =2^x \]
于是所求的 \(x\) 就是几个等差数列求和.
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define ll long long
const ll inf=0x7fffffff/27.11;
const ll maxn=200005;
ll i,j,t,n,m,l,r,k,z,y,x;
vector <ll> prime,fac;
vector <ll>::iterator vi;
ll f[maxn];
bool isp[maxn];
ll T,phi,ans,q;
inline void getprime()
{
ll i,j,t;
memset(isp,true,sizeof(isp));
prime.clear();
for (i=2;i<=maxn;i++) if (isp[i])
{
for (j=2*i;j<=maxn;j+=i) isp[j]=false;
prime.push_back(i);
}
}
inline void getfac(ll n)
{
ll i,j,t=sqrt(n+0.5);
phi=n;
fac.clear();
for (vi=prime.begin();vi!=prime.end() && *vi<=t;vi++) if (n%(*vi)==0)
{
phi=phi/(*vi)*(*vi-1);
fac.push_back(*vi);
while (n%(*vi)==0) n/=*vi;
}
if (n>1)
{
phi=phi/n*(n-1);
fac.push_back(n);
}
}
inline ll qpow(ll a,ll b,ll m)
{
ll i,j,t=1;
while (b)
{
if (b&1) t=t*a%m;
a=a*a%m;
b>>=1;
}
return t;
}
inline ll index(ll a,ll n)
{
ll i,j,t,ans=0;
i=a;
while (i<=n)
{
t=(ll)n/i;
ans+=t*(t+1)/2*i;
i*=a;
}
return ans;
}
int main()
{
getprime();
scanf("%lld",&T);
while (T--)
{
scanf("%lld%lld%lld",&n,&m,&q);
getfac(m);
f[1]=1%m;
for (i=2;i<=n;i++)
{
t=i;
for (vi=fac.begin();vi!=fac.end() && t>=*vi;vi++) while (t%(*vi)==0) t/=*vi;
f[i]=f[i-1]*qpow(t,i,m)%m;
}
while (q--)
{
scanf("%lld",&r);
if (m==1)
{
printf("0\n");
continue;
}
ans=f[n]*qpow(f[n-r],phi-1,m)%m*qpow(f[r],phi-1,m)%m;
for (vi=fac.begin();vi!=fac.end() && *vi<=n;vi++)
{
t=index(*vi,n)-index(*vi,r)-index(*vi,n-r);
ans=ans*qpow(*vi,t,m)%m;
}
printf("%lld\n",ans);
}
}
return 0;
}