ZOJ 3557 How Many Sets II lucas 定理

本文主要是介绍ZOJ 3557 How Many Sets II lucas 定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

插空法 大组合数取余

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;//求整数x和y，使得ax+by=d, 且|x|+|y|最小。其中d=gcd(a,b) 
void gcd(LL a, LL b, LL& d, LL& x, LL& y)
{if(!b){d = a;x = 1;y = 0;}else{gcd(b, a%b, d, y, x);y -= x * (a/b);}
}
//计算模n下a的逆。如果不存在逆， 返回-1 
LL inv(LL a, LL n)
{LL d, x, y;gcd(a, n, d, x, y);return d == 1 ? (x+n)%n : -1;
}
LL cm(LL n, LL m, LL p)
{LL ans1 = 1, ans2 = 1;while(m){ans1 = ans1*n%p;ans2 = ans2*m%p;n--;m--; }return ans1*inv(ans2, p)%p;
}
LL lucas(LL n, LL m, LL p)
{if(m == 0)return 1;return lucas(n/p, m/p, p)*cm(n%p, m%p, p)%p;
}
int main()
{LL n, m, p;while(scanf("%lld %lld %lld", &n, &m, &p) != EOF){		printf("%lld\n", lucas(n-2*m+1+m, m, p));}return 0;
}

这篇关于ZOJ 3557 How Many Sets II lucas 定理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---