【挑战赛16A】【取石子】【组合数学】

链接:https://www.nowcoder.com/acm/contest/113/A

来源:牛客网

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

题目描给出四堆石子,石子数分别为a,b,c,d。规定每次只能从堆顶取走石子,问取走所有石子的方案数。
输入描述:
在一行内读入四个由空格分隔的整数a,b,c,d, 输入均为不超过500的正整数
输出描述:
输出一个整数表示答案,答案对10^9+7
示例1
输入
3 5 4 2
输出
2522520
备注:
输入均为不超过500的正整数

题目分析:每堆石子内部的顺序已经确定,只有堆之间的顺序不确定,如果正面思考如何排序很难入手,反正最后都是要取出来放到一条线上,所以不如直接看作是在一个线上取相应多少的石子到相应的堆中,种类数也就是C(a+b+c+d,a) *C(b+c+d,b) * C(c+d,c)=(a+b+c+d)!/(a!b!c!d!)。利用逆元进行取模即可

 #include<iostream>
#include<cstdio>
using namespace std;
const long long mod=1e9+;
long long qaq(long long x)
{
long long ans=;
for(long long i = ; i <= x ; i++)
{
ans=(ans*i)%mod;
}
return ans;
}
long long mypow(long long x,long long y)
{
long long ans=;
while(y)
{
//cout <<x << endl;
if(y&)ans=(ans*x)%mod;
x=((x%mod)*(x%mod))%mod;
y/=; }
return ans;
}
int main()
{
long long a,b,c,d;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
long long qwq=qaq(a+b+c+d)%mod;
long long orz1=qaq(a)%mod;
long long orz2=qaq(b)%mod;
long long orz3=qaq(c)%mod;
long long orz4=qaq(d)%mod;
long long orz5=(((((orz1*orz2)%mod)*orz3)%mod)*orz4)%mod;
long long endd=qwq*mypow(orz5,mod-)%mod;
cout << endd<<endl;
return ;
}
上一篇:敏捷团队中的QA由来


下一篇:Deamon Thread 讲解