这个问题的答案是使用Lucas定理计算模质数的大二项式系数。以下是使用该技术解决该问题的解决方案:这里。
现在我的问题是:
- 似乎我的代码会因变量溢出而在数据增加时过期。有没有处理这种情况的方法?
- 是否有其他方法可以不使用定理来解决此问题?
编辑:请注���,由于这是一个OI或ACM问题,除原始库以外的外部库不被允许。
下面是代码:
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define N 100010
long long mod_pow(int a,int n,int p)
{
long long ret=1;
long long A=a;
while(n)
{
if (n & 1)
ret=(ret*A)%p;
A=(A*A)%p;
n>>=1;
}
return ret;
}
long long factorial[N];
void init(long long p)
{
factorial[0] = 1;
for(int i = 1;i <= p;i++)
factorial[i] = factorial[i-1]*i%p;
//for(int i = 0;i < p;i++)
//ni[i] = mod_pow(factorial[i],p-2,p);
}
long long Lucas(long long a,long long k,long long p)
{
long long re = 1;
while(a && k)
{
long long aa = a%p;long long bb = k%p;
if(aa < bb) return 0;
re = re*factorial[aa]*mod_pow(factorial[bb]*factorial[aa-bb]%p,p-2,p)%p;
a /= p;
k /= p;
}
return re;
}
int main()
{
int t;
cin >> t;
while(t--)
{
long long n,m,p;
cin >> n >> m >> p;
init(p);
cout << Lucas(n+m,m,p) << "\n";
}
return 0;
}
mod_pow
函数实现了这一点,并成功地使用了long long
。 - M Oehm