2

Нужно найти сумму сочетаний: на вход дается 3 числа: n, m, l (1<= n, m, l <= 10^6)

введите сюда описание изображения

пробовал через itertools, но использует слишком много памяти при больших тестах, math.comb не работает на данной версии Python, пробовал через массив факториалов и на Python и на C++, также не получается и с модульной арифметикой.

Мое неправильное решение на Python:

def C(n, m, mod):
    ans = 1
    for i in range(n - m + 1, n + 1):
        ans = ans * i
    for i in range(1, m + 1):
        ans /= i
    return int(ans) % mod


def main():
    n, m, l = map(int, input().split())
    if n < m: return 0
    if n == m: return 1
    mod = 1000000007
    c = C(n, m, mod)
    print(c)
    answer = 0
    for k in range(m, l * m + 1):
        if n < k: return answer
        if k % m == 0:
            answer = (answer + c % mod) % mod
        c = (c * (n - k) // (k + 1)) % mod
    return answer % mod


print(main())

Решение на C++:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


long long n, m, l, mod = 1e9 + 7, ans;

long long fastpow(long long a, long long n)
{
    if (n == 1) {return a;}
    if (n % 2) {return fastpow(a, n / 2) * fastpow(a, n / 2 + 1) % mod;}
    return fastpow(a, n / 2) * fastpow(a, n / 2) % mod;
}

int main()
{
    cin >> n >> m >> l;
    vector <long long> fac(n + 2, 1);
    for (int i = 2; i <= n + 1; ++ i){fac[i] = fac[i - 1] * i % mod;}
    for (int k = 1; k <= min(l, n / m); ++k){
        ans += (fac[n] * fastpow(fac[n - m * k] * fac[m * k] % mod, mod - 2) % mod) % mod;
    }
    cout << ans;
    return 0;
}
  • память: 256 мегабайт
  • время: 5 секунд
  • тесты для примера:
  • ввод: 3 1 3 вывод: 7
  • ввод: 3 4 5 вывод: 0
  • ввод: 999999 6 999999 вывод: 936253510
  • ввод: 1000000 1000000 1000000 вывод: 1
2
  • Вам не надо искать сумму, вам надо искать остаток. Кстати, уверен, что не "остаток при делении на 1000000000 плюс семь", а "остаток при делении на 1000000007". Да, а где URL проверялки, есть? И, кстати, какие ограничения на m, n, l?
    – Harry
    Commented 9 июл. 2023 в 10:39
  • да, модуль будет 1000000007, все числа не превосходят 10^6, ограничения по памяти не более 256 мегабайт, 5 секунд по времени Commented 9 июл. 2023 в 10:50

1 ответ 1

2

Не хотите попробовать этот код?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


unsigned long long iqpow(unsigned long long x,
                         unsigned long long e,
                         unsigned long long p)
{
    unsigned long long res = 1;
    x %= p;
    for(;e;e>>=1)
    {
        if (e&1) res = (res*x)%p;
        x = (x*x)%p;
    }
    return res;
}

int main()
{
    unsigned long long n, m, l, mod = 1000000007, ans = 0;
    cin >> n >> m >> l;
    vector <unsigned long long> fac(n + 2, 1);
    for (int i = 2; i <= n + 1; ++ i){fac[i] = fac[i - 1] * i % mod;}

    for (int k = 1; k <= l && m*k <= n; ++k)
    {
        ans = (ans + (fac[n] * iqpow(fac[n - m * k] * fac[m * k] % mod, mod - 2, mod) % mod)) % mod;
    }
    cout << ans;
    return 0;
}

В С++ вы как минимум неверно вычисляли ans (молчу уж про "быстрое" возведение в степень...) Для теста 999999 6 999999 ответ 936253510 получился за 40 мс.

С Python разбирайтесь сами: не мой язык...

3
  • благодарю, код правильный Commented 9 июл. 2023 в 11:25
  • 1
    Если кому интересно, в вопросе и в ответе для рассчёта обратной величины по модулю применена малая теорема Ферма. Commented 11 июл. 2023 в 22:53
  • @StanislavVolodarskiy И именно поэтому я решительно требовал скобочки в вопросе вокруг 10^9+7 :)
    – Harry
    Commented 12 июл. 2023 в 5:14

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.