牛客NOIP暑期七天营-提高组6C：分班问题 （组合数）

题意：A班有N个人，B班有M个人，现在要组成一个新的班级C班，为了公平，从AB班各抽相同人数的人。 现在求所有方案中，人数之和是多少。

思路：即求Σ k*C(N,k)*C(M,k);    先忽略这个外层的k，看看两个组合数乘积的和怎么求。 

显然Σ C(N,k)*C(M,k)=C(N+M,N);  因为C(N,k)=C(N,N-k)； 所以可以看成在N中选N-k个，M中选k个，所以就是一个组合数。

现在看怎么处理这个k。 注意到k*C(N,k)=N*C(N-1,k-1);    就可以搞了：  Σ k*C(N,k)*C(M,k)=Σ N*C(N-1,k-1)*C(M,k)=C(N+M-1,N-1)；

然后Lucas搞就可以了。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int Mod=19260817;
const int maxn=19260817;
int f[maxn],rev[maxn];
int qpow(int a,int x){
    int res=1; while(x){
        if(x&1) res=1LL*res*a%Mod;
        x>>=1; a=1LL*a*a%Mod;
    } return res;
}
void init()
{
    f[0]=rev[0]=1;
    rep(i,1,maxn-1) f[i]=1LL*f[i-1]*i%Mod;
    rev[maxn-1]=qpow(f[maxn-1],Mod-2);
    for(int i=maxn-2;i>=1;i--) rev[i]=1LL*rev[i+1]*(i+1)%Mod;
}
int C(int N,int M)
{
    if(N<M) return 0;
    return 1LL*f[N]*rev[M]%Mod*rev[N-M]%Mod;
}
int Lucas(ll N,ll M)
{
    if(M==0) return 1;
    return 1LL*Lucas(N/Mod,M/Mod)*C(N%Mod,M%Mod)%Mod;
}
int main()
{
    init();
    int T; ll N,M;
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld",&N,&M);
        printf("%d
",2LL*M%Mod*Lucas(N+M-1,N-1)%Mod);
    }
    return 0;
}