ルーカステンプレート
LucasはC(n,m)%pの値を求めるために用いられ,n,mが大きく,p(一定素数)が1 e 6未満の場合に適用される.
テンプレート:
#include
#include
#include
#define ll long long
using namespace std;
const int maxn = 1e6+5;
const int mod = 1e9+7;
using namespace std;
ll quick_mod(ll a, ll b, ll c)
{
ll ans = 1;
while(b)
{
if(b & 1)
ans = (ans*a)%c;
b>>=1;
a = (a*a)%c;
}
return ans;
}
ll fac[maxn];
void Get_Fac(ll m)///m!
{
fac[0] = 1;
for(int i=1; i<=m; i++)
fac[i] = (fac[i-1]*i) % m;
}
ll Lucas(ll n, ll m, ll p)
{
ll ans = 1;
while(n && m)
{
ll a = n % p;
ll b = m % p;
if(a < b)
return 0;
ans = ( (ans*fac[a]%p) * (quick_mod(fac[b]*fac[a-b]%p,p-2,p)) ) % p;
n /= p;
m /= p;
}
return ans;
}
int main()
{
ll n, m, p;
cin>>n>>m>>p;
Get_Fac(p);
cout<