• 周四. 12月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2021“MINIEYE杯”中国大学生算法设计超级联赛(7) 1004 Link with Balls

admin

11月 28, 2021

题意:给你n对桶,第i对能分别提供出来0,1,2,…,i-1个球以及0,i,2i,3i,…个球,问凑m个球的方案数

第i对的生成函数为

[m (1+x+x^2+…+x^i)(1+x^i+x^{2i}+…)
]

等比数列求和有

[dfrac{x^{i+1}-1}{x-1} imes dfrac{1}{1-x^i}
]

考虑生成函数的实际意义,把n个生成函数乘起来,答案就是(x^m)的系数

[prodlimits_{i=2}^{n+1}dfrac{x^i-1}{x-1}prodlimits_{i=1}^{n}{dfrac{1}{1-x^i}}
]

抽出来前面的n+1项和后面的第1项,有

[dfrac{x^{n+1}-1}{x-1} imes dfrac{1}{x-1}(-1)^nprodlimits_{i=2}^{n}dfrac{x^i-1}{x-1}dfrac{1}{x^i-1}
]

后面都被干掉了,把下面的1+1+(n-1)个(x-1)合并起来有

[(-1)^ndfrac{x^{n+1}-1}{(x-1)^{n+1}}
]

把分母用广义二项式定理展开有

[(-1)^n(x^{n+1}-1)sumlimits_{k=0}^infty mathbf{C}_{-(n+1)}^{k}(-1)^kx^k(-1)^{-(n+1)-k}
]

对组合数做负指标变换

[(-1)^n(x^{n+1}-1)sumlimits_{k=0}^infty mathbf{C}_{k+(n+1)-1}^{k}(-1)^kx^k(-1)^{-(n+1)-k}
]

合并一下(-1)的指数,发现能提出来,和前面的合并

[(1-x^{n+1})sumlimits_{k=0}^infty mathbf{C}_{k+n}^kx^k
]

至此可以做了,我们要找(x^m)的系数

首先令k=m,得到(mathbf{C}_{m+n}^m)

然后令k=m-(n+1),得到(-mathbf{C}_{m-1}^{m-(n+1)}),也即(-mathbf{C}_{m-1}^{n})

注意前面有个负号

最终答案为(mathbf{C}_{m+n}^m – mathbf{C}_{m-1}^n)

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2000006;

int fac[MAXN];
int inv[MAXN];

int qpow(int x,int y=MOD-2){
  int ret=1,base=x;
  while(y){
    if(y&1) ret=ret*base%MOD;
    base=base*base%MOD;
    y>>=1;
  }
  return ret;
}

int c(int x,int y){
  if(x<y) return 0;
  return fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}

signed main(){
  fac[0]=1;
  for(int i=1;i<=2000000;i++)
    fac[i]=fac[i-1]*i%MOD;
  inv[2000000]=qpow(fac[2000000]);
  for(int i=2000000-1;i>=1;i--)
    inv[i]=inv[i+1]*(i+1)%MOD;
  int T;
  cin>>T;
  while(T--){
    int n,m;
    cin>>n>>m;
    cout<<(c(n+m,m)-c(m-1,n)+MOD)%MOD<<endl;
  }
}

本文来自博客园,作者:GhostCai,转载请注明原文链接:https://www.cnblogs.com/ghostcai/p/15125540.html

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注