Cod sursa(job #3373274)

Utilizator MirceaCUCUSirghe Mircea Anton MirceaCUCU Data 6 noiembrie 2026 14:17:29
Problema Sandokan Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <bits/stdc++.h>
using namespace std;

#define MOD 2000003

ifstream in("sandokan.in");
ofstream out("sandokan.out");

int fact[5001],invfact[5001];

void factoriale(int n)
{
    fact[0]=1;
    for(int i=1;i<=n;i++){
        fact[i]=(1LL*fact[i-1]*i)%MOD;
    }
}

int dot_product(int baza, int p)
{
    int rez=1;
    while(p>0)
    {
        if(p&1){
            rez=(1LL*rez*baza)%MOD;
        }
        p/=2;
        baza=(1LL*baza*baza)%MOD;
    }
    return rez;
}

void inversmodfactoriale(int n)
{
    invfact[n]=dot_product(fact[n], MOD-2);
    for(int i=n-1;i>=0;i--){
        invfact[i]=(1LL*invfact[i+1]*(i+1))%MOD;
    }
}

int main()
{
    int n,k,sol=1,r;
    in>>n>>k;
    for(int i=1;i<=n;i++){int x; in>>x;}
    r=(n-1)%(k-1)+1;
    factoriale(n);
    inversmodfactoriale(n);
    sol=fact[n-1];
    sol=(1LL*sol*invfact[r-1])%MOD;
    sol=(1LL*sol*invfact[n-r])%MOD;
    out<<sol;
    return 0;
}