【问题描述】
商店里出售n种不同品种的花。为了装饰桌面,你打算买m支花回家。你觉得放两支一样的花很难看,因此每种品种的花最多买1支。求总共有几种不同的买花的方案?答案可能很大,输出答案mod p的值。
【输入格式】
一行3个整数n,m,p,意义如题所述。
【输出格式】
一个整数,表示买花的方案数。
【输入输出样例1】
flower.in | flower.out |
4 2 5 | 1 |
见选手目录下的flower / flower1.in与flower / flower1.out
【输入输出样例1说明】
用数字1,2,3,4来表示花的种类的话,4种花里买各不相同的2支的方案有(1,2)、(1,3)、(1,4)、(2,3)、(2,4)、(3,4),共6种方案,模5后余数是1。
【输入输出样例2】
见选手目录下的flower / flower2.in与flower / flower2.out
【数据范围】
对于30%的数据,n,m≤10
对于50%的数据,n,m≤1000
对于80%的数据,1≤m≤n≤50,000
对于100%的数据,1≤m≤n≤1,000,000,p≤1,000,000,000
/*
鲁卡斯定理的适用条件:p为质数(sth原话:p为任意数我也不会求),因为逆元不能直接算,所以必须要分析组合数性质,这个题其实也可作为取模组合数的模板题
分析组合数的公式,首先确定这个数一定是一个整数,也就是说我们只需要分子分母各自分解质因数,然后把分子中出现在分母中的质因数对应减掉其出现次数就行了,暴力分解会稍微慢一点,我们用nlogn的筛法解决,一个数倍一个质数筛掉,分解成两个因子,然后这两个因子继续分解质因数
两篇文章
①http://blog.csdn.net/acdreamers/article/details/8220787
②http://blog.csdn.net/acdreamers/article/details/8037918
*/
#include <cstdio>
#include <cmath> int cnt[],n,m,i,j,r,v[],d[];
long long p,ans; int main()
{
freopen("flower.in", "r", stdin);
freopen("flower.out", "w", stdout);
scanf("%d%d%I64d", &n, &m, &p);
for (i=m+; i<=n; ++i) cnt[i] = ;
for (i=; i<=n-m; ++i) cnt[i] -= ; for (i=; i<=n; ++i)
if (!v[i])
{
for (j=i+i; j<=n; j+=i)
{
v[j] = ;
d[j] = i;
}
}
for (i=n; i>=; --i)
if (d[i] > )
{
cnt[d[i]] += cnt[i];
cnt[i/d[i]] += cnt[i];
cnt[i] = ;
}
ans = ;
for (i=; i<=n; ++i)
for (j=; j<=cnt[i]; ++j) ans = ans*i%p;
printf("%I64d\n", ans);
return ;
}