插空法 大组合数取余

#include 
  
   
#include 
   
     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; }