HDU 3037(Lucas定理)

对于很大的组合数不能用C(n, m) = C(n - 1, m) + C(n-1, m -1)来求,这里就用到Lucas定理。

模板题: hdu3037:模板如下:

#include <cstdio>

using namespace std;
const int maxn = ;
typedef long long ll;
ll F[maxn];
//求1-p所有的阶乘模上p
void init(ll p)
{
F[] = ;
for (int i = ; i <= p; i++)
F[i] = F[i - ] * i % p;
}
//求逆元
ll inv(ll a, ll m)
{
if (a == ) return ;
return inv(m % a, m) * (m - m / a) % m;
}
//求C n m %p之后的值
ll Lucas(ll n, ll m, ll p)
{
ll ans = ;
while (n && m)
{
ll a = n % p;
ll b = m % p;
if (a < b) return ;
ans = ans * F[a] % p * inv(F[b] * F[a - b] % p, p) % p;
n /= p;
m /= p;
}
return ans;
}
int main()
{
int T, n, m, p;
scanf("%d", &T);
while (T--)
{
scanf("%d %d %d", &n, &m, &p);
init(p);
printf("%d\n", (int)Lucas(n + m, m, p));
}
return ;
}
上一篇:spring +hibernate 启动优化【转】


下一篇:Apriori算法-数组-C语言