Rezolvare completă PbInfo #1195 NMult

Se consideră trei numere naturale nenule n, k și w.

Cerința

Să se scrie un program care determină numărul m al mulțimilor de forma {x[1], x[2], … ,x[k]} având ca elemente numere naturale nenule, ce satisfac simultan condițiile:

  • 1 ≤ x[1] < x[2] < ... < x[k] ≤ n
  • x[i+1] - x[i] ≥ w, 1 ≤ i ≤ k - 1

Date de intrare

Fișierul de intrare nmult.in conține pe prima linie trei numere naturale nenule n, k, w separate prin câte un spaţiu, cu semnificaţia de mai sus.

Date de ieșire

Fișierul de ieșire nmult.out va conține pe prima linie restul împărţirii numărului m la 666013.

Restricții și precizări

  • 1 ≤ n, k, w ≤ 1.000.000;

Exemplul 1

nmult.in

5 2 2

nmult.out

6

Explicație

n=5, k=2, w=2

Există 6 mulțimi cu 2 elemente, astfel încât diferența între oricare 2 termeni consecutivi să fie cel puțin 2: {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5}

Exemplul 2

nmult.in

10 3 4

nmult.out

4

Explicație

n=10, k=3, w=4

Există 4 mulțimi cu 3 elemente, astfel încât diferența între oricare 2 termeni consecutivi să fie cel puțin 4: {1,5,9}, {1,5,10}, {1,6,10}, {2,6,10}.

Exemplul 3

nmult.in

10 4 4

nmult.out

0

Explicație

n=10, k=4, w=4

Nu există nicio mulțime de 4 elemente în care condițiile să fie îndeplinite.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema NMult:

// sursa cu combinari + Legendre
// prof. Chesca Ciprian

#include <fstream>
#define M 666013
#define nmax 1000001

using namespace std;

int n,k,w;
ifstream f("nmult.in");
ofstream g("nmult.out");


char v[nmax];
int p[nmax/10],desc[nmax/10],nr=0;


// Ciurul lui Eratostene
void ciur(int n)
{
  int i, j;
  for (i = 2; i <= n; ++i) {
    if (v[i] == 0) {
      p[++nr]=i;
      for (j = i + i; j <= n; j += i) {
        v[j] = 1;
      }}}

}

// descompunere in factori primi a lui x! cu Legendre
void dsc(int x,int op)
{
long long i,s,pp,ok;

for(i=1;i<=nr;i++)
{
    s=0;pp=p[i];ok=1;
    while (ok)
    {
        s=s+x/pp;
        if (x/pp==0) ok=0;
        pp=pp*p[i];

    }
    if (op==1)  desc[i]+=s;
        else    desc[i]-=s;
}}


int mdl()
{
long long i,j,pp=1,r=1;
for(i=1;i<=nr;i++)
{
    pp = 1;
    for(j=1;j<=desc[i];j++)
        pp = (pp*p[i]) % M;

    r = (r*pp) % M;

}
return r;
}


int main()
{

    f>>n>>k>>w;
    ciur(n-(w-1)*(k-1));
    dsc(n-(w-1)*(k-1),1);
    dsc(k,0);
    dsc(n-(w-1)*(k-1)-k,0);
    if (n-(k-1)*(w-1)<k) g<<"0"<<"
";
    else g<<mdl();

    f.close();
    g.close();

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1195 NMult

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1195 NMult de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!