腾讯2018秋招笔试真题-小Q的歌单

r囧r小猫 2022-05-19 13:29 323阅读 0赞

# 小Q的歌单 #

> 【题目描述】小 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

解题思路：  
1）歌单存在时要满足的条件  
i \* a <= k && (k - a \* i) % b == 0 && (k - a \* i) / b <= y  
2）需要用得到的公式：  
从i个不同元素中，选择j个的组合数目，记为c\[i\]\[j\]，则满足  
c\[i\]\[j\] = (c\[i - 1\]\[j - 1\] + c\[i - 1\]\[j\])

### 代码 ###

#include <stdio.h>
    #include<stdlib.h>  //system()
    
    using namespace std;
    long long c[105][105];
    const int mod = 1000000007;
    void init() {
        c[0][0] = 1;
        for (int i = 1; i <= 100; i++) {
            c[i][0] = 1;
            for (int j = 1; j <= 100; j++)
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
        }
    }
    int main() {
        int k, a, b, x, y;
        long long ans = 0;
        init();
        scanf_s("%d", &k);
        scanf_s("%d%d%d%d", &a, &x, &b, &y);
        for (int i = 0; i <= x; i++) {
            if (i * a <= k && (k - a * i) % b == 0 && (k - a * i) / b <= y)
                ans = (ans + (c[x][i] * c[y][(k - a * i) / b]) % mod) % mod;
        }
        printf("%lld\n", ans);
        system("pause");
        return 0;
    }

注：参考了牛客网解答。