0

我有一个任务有问题，所以如果你能帮助我一点。

数字是“幸运”或“不幸”。仅当每个数字 7 或每个数字都是 4 时，数字才是“幸运”。因此，“幸运”数字是例如 4、44、7、77。“不幸”是其他数字。
您将获得 n 个元素的序列和数字 K。您的任务是计算所有可能的 k 元素子序列的数量，它们满足一个条件。条件是子序列中不能有两个相同的“幸运”数字。因此，例如不能有 77 和 77... 所有可能的 k 元素子序列的输出数 mod 10^9+7 0 < N,K < 10^5 

Few examples:
Input:

5 2
7 7 3 7 77
Output:

7

Input:

5 3
3 7 77 7 77
Output:

4

Input:

34 17
14 14 14 ... 14 14 14
Output:

333606206

我的代码似乎可以工作，但是当我尝试计算二项式系数时它太慢了。我正在使用地图。在字符串中，我以字符串格式存储数字。在地图的第二个 - int - 部分是数字，表示该数字（在第一个地图参数中）使用了多少次。所以现在我把每一个“倒霉”的数字都存储在一起了。每个相同的“幸运”数字也在一起。当我像这样存储它时，我只计算所有乘法。例如：

Input 
5 2
3 7 7 77 7
Are stored like this:  map["other"] = 1 map["7"] = 3 map["77"] = 1 
Because k = 2 --> result is: 1*3 + 1*1 + 1*3 = 7.

我认为问题在于计算二项式系数。对于第三个示例，它需要计算（34 选择 17）并且计算时间很长。我找到了这篇文章和这篇文章，但我不明白他们是如何解决这个问题的。

我的代码：

#include<iostream>
#include<string>
#include<map>
#include <algorithm>
#include <vector>

using namespace std;

int binomialCoeff(int n, int k)
{
    // Base Cases
    if (k == 0 || k == n)
        return 1;

    // Recur
    return  binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k);
}

int main()
{
    int n, k;
    cin >> n >> k;
    map<string, int> mapa;  // create map, string is a number, int represents number of used string-stored numbers ---> so if 7 was used two times, in the map it will be stored like this mapa["7"] == 2 and so on)
    for (int i = 0; i < n; i++)  // I will load number as string, if this number is "lucky" - digist are all 7 or all 4
    {                            // every "unlucky" numbers are together, as well as all same "lucky" numbers ---> so 77 and 77 will be stored in one element....
        string number;
        cin >> number;
        char digit = number[0];
        bool lucky = false;
        if (digit == '7' || digit == '4')
            lucky = true;
        for (int j = 1; j < number.length(); j++) {
            if (digit != '7' && digit != '4')
                break;
            if (number[j] != digit) {
                lucky = false;
                break;
            }
        }
        if (lucky)
            mapa[number]++;
        else
            mapa["other"]++;
    }
    vector<bool> v(mapa.size());
    bool lack = k > mapa.size(); //lack of elements in map --> it is when mapa.size() < k; i. e. number of elements in array can't make k-element subsequence.
    int rest = lack ? k - mapa.size() + 1 : 1;  // how many elements from "unlucky" numbers I must choose, so it makes base for binomial coefficient (n choose rest)
    if (lack)  //if lack is true, different size of vector
        fill(v.begin() + mapa.size(), v.end(), true);
    else
        fill(v.begin() + k, v.end(), true);
    int *array = new int[mapa.size()];   //easier to manipulate with array for me
    int sum = 0;  
    int product = 1;
    int index = 0; 
    for (map<string, int> ::iterator pos = mapa.begin(); pos != mapa.end(); ++pos)  // create array from map
    {
        if (lack && pos->first == "other") {    //if lack of elements in map, the number in elemets representing "unlucky" numbers will be binomial coefficient (mapa["other] choose rest)
            array[index++] = binomialCoeff(mapa["other"], rest);
            continue;
        }
        array[index++] = pos->second;
    }
    do {   // this will create every posible multiplication for k-elements subsequences
        product = 1;
        for (int i = 0; i < mapa.size(); ++i) {
            if (!v[i]) {
                product *= array[i];
            }
        }
        sum += product;
    } while (next_permutation(v.begin(), v.end()));
    if (mapa["other"] >= k && mapa.size() > 1) {   // if number of "unlucky" numbers is bigger than k, we need to compute all possible  k-elements subsequences just from "unlucky" number, so binomial coefficient (mapa["other] choose k)
        sum += binomialCoeff(mapa["other"], k);
    }
    cout << sum % 1000000007 << endl;
}
4

0 回答 0