https://acm.hdu.edu.cn/showproblem.php?pid=7047
题意:
2*n个筐,每个筐里的球个数无限。第2*x个框至多取x个球,第2*x-1个框只能取x的倍数个球。
问取出m个球的方案数
至多取x-1个球的筐和只能取x的倍数个球的筐放在一起可以看作是可以取任意个球的筐
所以第2个筐到第2n-1个筐构成了n-1个可以取任意球的筐,第1个筐也是可以取任意球,第2n个筐可以取0—n个球
所以相当于n个可以取任意球的筐和1个可以取0—n个球的筐
枚举从可以取0—n个球的筐中取i个
那就是在n个筐里任意取够m-i个球
根据组合数学中的插板法,答案是C(m-i+n-1,n-1)
所以答案是∑ C(m-i+n-1,n-1) i∈[0,min(n,m)]
∑ C(m-i+n-1,n-1) = C(m-1,n-1)+C(m,n-1)+C(m+1,n-1)+……+C(m+n-1,n-1)
相当于问杨辉三角第n-1列,第m-1行到第m+n-1行的和
由A1+C=B得 A1=B-C
所以A1+A2+A3+A4=B-C+A2+A3+A4=B+A2+A3+A4-C=D-C
所以∑ C(m-i+n-1,n-1) = C(m+n,n)-C(m-1,n)
#include<bits/stdc++.h> using namespace std; #define N 2000001 const int mod=1e9+7; int fac[N],inv[N]; int poww(int a,int b) { int c=1; for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) c=1ll*c*a%mod; return c; } int C(int n,int m) { if(n<m) return 0; int w=1ll*fac[n]*inv[m]%mod*inv[n-m]%mod; return w; } int main() { fac[0]=1; for(int i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%mod; inv[N-1]=poww(fac[N-1],mod-2); for(int i=N-2;i>=0;--i) inv[i]=1ll*inv[i+1]*(i+1)%mod; int T,n,m; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); printf("%d\n",(C(n+m,n)-C(m-1,n)+mod)%mod); } }
hdu7047 /2021“MINIEYE杯”中国大学生算法设计超级联赛(7) 1004 Link with Balls