小Q的歌单

问题描述–2018年腾讯秋招笔试真题

小Q有X首长度为A的不同的歌和Y首长度为B的不同的歌，现在小Q想用这些歌组成一个总长度正好为K的歌单，每首歌最多只能在歌单中出现一次，在不考虑歌单内歌曲的先后顺序的情况下，请问有多少种组成歌单的方法。

输入描述

每个输入包含一个测试用例。
每个测试用例的第一行包含一个整数，表示歌单的总长度K（1<=K<=1000）。
接下来的一行包含四个正整数，分别表示歌的第一种长度，A（A<=10)和数量X（X<=100）以及歌的第二种长度B（B<=10）和数量Y（Y<=100）。保证A不等于B。

输出描述

输出一个整数，表示组成歌单的方法取模。因为答案可能会很大，输出对1000000007取模的结果。

输入示例

5  
2 3 3 3

输出示例

9

结题思路

假设a首A长度的歌曲和b首B长度的歌曲组成歌单，那么应该满足下列方程

a*A+b*B=K  
a<=X;  
b<=Y;

那么，只需要对a和b进行排列组合就可以，输出只需要对这个结果取模即可。

代码

#include<iostream>
#include<cmath>

using namespace std;

long C(int m,int n){
	long res=0;
	if(0==m || 0==n){
		return 1;
	}
	if(1==m){
		return n;
	}
	long x=1;
	long y=n;
	for(int i=1,j=n;i<=m;i++,j--){
		x=x*i;
		y=y*j;
	}
	return y/x;
} 

int main(){
	const int mod=1000000007;
	int k;
	cin>>k;
	int A,B,X,Y;
	cin>>A;
	cin>>X;
	cin>>B;
	cin>>Y;
	
	long res=0;
	long temp;
	for(int i=0;i<X;i++){
		for(int j=0;j<Y;j++){
			temp=i*A+j*B;
			if(temp==k){
			res+=C(i,X)*C(j,Y);	
			}
			else if(temp>k){
				break;
			}
		}
		temp=i*A;
		if(temp>k){
			break;
		}
	}
	
	cout<< res%mod<<endl;
	return 0;
}

这是我的代码，因为我是事后写的，不一定能通过所有的测试用例，欢迎大家指出错误，写完博客，放松下