Нужно найти сумму сочетаний: на вход дается 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