链接：https://ac.nowcoder.com/acm/problem/15442
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

wyh非常喜欢lol游戏，一天，他听说学校要选拔lol队员，他非常高兴的就去了，选拔规则是，一共有N个评委，每个评委根据线上对线能力和打团能力给出一个[0,M]之间的一个整数作为分数，然后取平均值，wyh学长非常好奇，他想知道有多少种这样的情况：

平均分等于其中某一位评委给的分数

例如2个评委，给打的分数都是1分，那么此时平均分是1分，即等于第一个评委的分数，又等于第二个评委的分数，这样答案是2

但是由于每个评委打的分都是在[0,M]之间，所以会有很多种情况。

现在请你帮助你们wyh学长数一下有多少种这样的情况，由于结果会很大，请你对1000000007取余

输入描述:

输入第一行一个整数T（1<=T<=110）
接下来有T组测试数据，对于每组测试数据输入2个数n和M(2<=n<=60,1<=M<=200)，代表有n个评委，每个评委的分数都在[0,M]之间的一个整数

输出描述:

对于每组测试数据，输出对应答案

示例1

输入

复制

1
3 1

输出

复制

6

说明


 

 

样例解释：

对于样例有以下几种打分情况是符合要求的

 

 

 

其中每种情况相等的可能性都是三个，比如0分的时候，平均分和第一位、第二位、第三位都相等，所以是3中情况，1的时候也同理，所以答案为6

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll dp[61][12005];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=0;i<=m;i++) dp[0][i]=1;
        for(int i=1;i<n;i++){
            for(int j=0;j<=i*m;j++){
                if(j<=m) dp[i][j]=dp[i-1][j];
                else dp[i][j]=((dp[i-1][j]-dp[i-1][j-m-1])%mod+mod)%mod;
            }
            if(i!=n-1){
                for(int j=1;j<=(i+1)*m;j++)
                dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
            }
        }
        ll ans=0;
        for(int i=0;i<=m;i++){
            ans+=dp[n-1][(n-1)*i];
            ans%=mod;
        }
        ans=ans*n%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

枚举+多元一次不定方程求非负整数解的组数

#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
const int mod=1e9+7;
ll c[12100][65];//记忆化组合数
int n,m;
ll ksm(ll a,ll b){
	ll s=1;
	while(b){
		if(b&1){
			a%=mod;
			s%=mod;
			s*=a;
		}
		a%=mod;
		a*=a;
		b>>=1;
	}
	return s%mod;
}
ll C(int n,int m){//求组合数
	if(m==0||m==n) return 1;
	if(m>n-m) m=n-m;
	if(c[n][m]) return c[n][m];
	ll up=1,down=1;
	for(int i=1;i<=m;i++){
		up=(up*(n-i+1))%mod;
		down=(down*i)%mod;
	}
	return c[n][m]=up*ksm(down,mod-2)%mod;
}
ll rc(ll n,ll k){//容斥原理求某个数>m的方程解的种数
	ll ans=0;
	for(int i=1;k+n-i*(m+1)-1>=n-1;i++){
		if(i&1) ans+=C(n,i)*C(k+n-i*(m+1)-1,n-1)%mod;
		else ans-=C(n,i)*C(k+n-i*(m+1)-1,n-1)%mod;
		ans%=mod;
	}
	return ans;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);	
		ll ans=0;
		for(int i=0;i<=m;i++){
			ans=(ans+n*C((n-1)*(i+1)-1,n-2))%mod;
			ans-=n*rc(n-1,(n-1)*i);
			ans=(ans%mod+mod)%mod;		
		}
		printf("%lld\n",ans);
	}	
	return 0;
}