题目:Saving Beans
题意:不超过n个球放入m个盒子方案数,盒子可以为空
解析:
Lucas。
通过隔板法,推出式子后可以在前面加一项递推到最后答案为。
代码:
#include <bits/stdc++.h> #define int long long using namespace std; const int Max=100005; int t,n,m,mod,mul[Max]; inline int c(int a,int b){return a*b<mod?a*b:a*b%mod;} inline int ksm(int a,int b,int c) { int ans=1; a%=mod; while(b) { if(b&1) ans=(ans*a)%mod; b>>=1; a=(a*a)%mod; } return ans; } inline int C(int n,int m) { if(n>=0&&m>=0&&n>=m) return c(c(mul[n],ksm(mul[m],mod-2,mod)),ksm(mul[n-m],mod-2,mod)); return 0; } inline int Lucas(int n,int m) { if(!m) return 1; return c(Lucas(n/mod,m/mod),C(n%mod,m%mod)); } signed main() { scanf("%lld",&t); while(t--) { scanf("%lld%lld%lld",&n,&m,&mod); mul[0]=1; for(int i=1;i<mod;i++) mul[i]=c(mul[i-1],i); printf("%lld\n",Lucas(n+m,m)); } return 0; }