Не понимаю в чем ошибка, требуется вывести ответ по модулю

Question

Программа должна найти сумму всех сочетаний, где k от 1 до l. Я использовал все через модуль. И формулу на картинке ниже.

Example_1:
Input: 3 1 3
Output: 7 


Example_2:  
Input: 3 4 3  
Output: 0  

Example_3:  
Input: 999999 6 999999  
Output: 936253510 


Example_4:  
Input: 1000000 1000000 1000000  
Output: 1

#include <iostream>

using namespace std;

typedef long long ll;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

ll norm(ll a, ll mod){
    return ((a % mod) + mod) % mod;
}

ll suma(ll a, ll b, ll mod){
    return norm(norm(a, mod) + norm(b, mod), mod);
}

ll minusong(ll a, ll b, ll mod){
    return norm(norm(a, mod) - norm(b, mod), mod);
}

ll mult(ll a, ll b, ll mod){
    return norm(norm(a, mod) * norm(b, mod), mod);
}

ll fast(ll a, ll n, ll mod){
    if(n == 0LL){
        return 1LL;
    }
    if(n % 2 == 1){
        return mult(a, fast(a, n - 1, mod), mod);
    }
    ll tmp = fast(a, n / 2, mod);
    return mult(tmp, tmp, mod);
}

ll div(ll a, ll b, ll mod){
    return mult(a, fast(b, mod - 2LL, mod), mod);
}

ll fact(ll n, ll mod){
    ll res = 1;
    for(ll i = 1; i <= n; i ++){
        res = mult(res, i, mod);
    }
    return res;
}

ll C(ll n, ll k, ll mod)
{    
    ll minusing = fact(minusong(n, k, mod), mod);
    ll factk = fact(k, mod);
    return div(fact(n, mod), mult(minusing, factk, mod), mod);
}

int main(){
    ll n, m, l;
    cin >> n >> m >> l;
    ll mod = 1e9 + 7;
    ll sumo = 0;
    if(n >= m){
        ll k = m;
        ll c = C(n, k, mod);
        sumo = suma(sumo, c, mod);
        for(ll i = 1; i <= l; i ++){
            k = mult(m, i, mod);
            if(n < k){
                break;
            }
            c = div(mult(c, minusong(n, k, mod), mod), suma(k, 1, mod), mod);
            sumo = suma(sumo, c, mod);
        }
    }
    cout << sumo;
}

Answer 1

Честно говоря, ваше решение мне не совсем понятно. Можно, я предложу свое?

#include <iostream>

using namespace std;

unsigned long long r[1000001] = {0};

unsigned long long inverse(unsigned long long k)
{
    return r[k];
}

int main()
{
    unsigned long long n, m, l, p = 1000000007;

    r[1] = 1;
    for (unsigned long long i=2; i< 1000001; ++i)
    r[i] = (p - (p/i) * r[p%i] % p) % p;

    cin >> n >> m >> l;

    unsigned long long C = 1, S = 0;

    for(unsigned long long k = 1; k <= l*m; ++k)
    {
        C = ((C * (n-k+1))%p * inverse(k)) %p;
        if (k%m == 0) S = (S + C)%p;
        if (C == 0) break;
    }
    cout << S;
}

БЛОГ НА HUSL

Не понимаю в чем ошибка, требуется вывести ответ по модулю

Ответы (1 шт):