У меня проблема с одной задачей, так что если вы могли бы мне немного помочь.
Числа «счастливые» или «несчастливые». Номер «счастливчик», только если каждый
цифра 7
или каждая цифра равна 4. Так что «счастливые» числа, например, 4, 44, 7, 77.
«Не повезло» остальные номера.
Вы получите последовательность из n элементов и число K. Ваша задача
вычислить количество всех возможных подпоследовательностей k-элементов, которые выполняют один
состояние. Условие состоит в том, что в подпоследовательности не должно быть двух одинаковых «счастливых» чисел. Так, например, не должно быть 77 и 77 …
Выведите число всех возможных k-элементов подпоследовательности mod 10 ^ 9 + 7
0 < N, K < 10 ^ 5Few 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;
}
Задача ещё не решена.
Других решений пока нет …