【HDU3037】Saving Beans

xiaoxiao2025-10-12  9

题目: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; }

 

转载请注明原文地址: https://www.6miu.com/read-5037783.html

最新回复(0)