Question

Dorel tocmai a învățat la școală despre permutări. El a reținut faptul că n persoane pot fi aranjate pe n locuri în n! moduri, unde n!=1⋅2⋅3⋅…⋅nn!=1⋅2⋅3⋅…⋅n. Pentru a vă pune pe voi la încercare Dorel mai alege un număr p și vă întreabă în câte moduri putem aranja n persoane numerotate de la 1 la n pe n locuri, numerotate şi ele de la 1 la n, astfel încât suma dintre numărul persoanei și numărul locului să fie divizibilă cu p?

Date de intrare
Programul citește de la tastatură numerele n și p, separate prin spații.

Date de ieșire
Programul va afișa pe ecran numărul m, reprezentând numărul de moduri cerut. Deoarece acest număr ar putea fi foarte mare, rezultatul se va afișa modulo 100019.

Restricții și precizări
1 ≤ p ≤ n ≤ 100.000
locurile și persoanele sunt numerotate de la 1 la n



Exemplu
Intrare

8 4
Ieșire

16
Explicație
Avem 8 persoane și 8 locuri. Persoanele 1 și 5 se pot așeza pe locurile 3 și 7 în 2! moduri, persoanele 2 și 6 pe locurile 2 și 6 în 2! moduri, persoanele 3 și 7 pe locurile 1 și 5 în 2! moduri, iar persoanele 4 și 8 pe locurile 4 și 8 în 2! moduri. În total vom avea 2 4 =16 moduri de aranjare.
Indicatii de rezolvare:
Cum suma dintre numărul persoanei și numărul locului este divizibilă cu p deducem că dacă numărul persoanei dă restul r nenul la împărțirea cu p, atunci numărul locului pe care este așezată trebuie să dea restul p-r la împărțirea cu p.

Deci pentru fiecare r nenul trebuie să avem tot atâtea numere care dau restul r la împărțirea cu p câte numere dau restul p-r. Acest lucru se întâmplă numai dacă n este divizibil cu p sau n+1 este divizibil cu p. Deci dacă n nu este divizibil cu p și n+1 nu este divizibil cu p, atunci numărul de moduri de aranjare a persoanelor este 0. Într-adevăr, în acest caz avem p ≥ 3 și vor exista n/p +1 locuri ce dau restul 1 la împărțirea cu p și numai n/p persoane ce dau restul p-1 la împărțirea cu p, deci va rămâne un loc neocupat.

Dacă n este divizibil cu p, atunci vor exista câte n/p persoane și locuri care dau același rest la împărțirea cu p. Cele n/p persoane care dau restul r, nenul, la împărțirea cu p se vor așeza pe cele n/p locuri ce dau restul p-r în (n/p)! moduri. De asemenea, cele n/p persoane ce dau restul 0 la împărțirea cu p se vor așeza pe cele n/p locuri ce dau restul 0 tot în (n/p)! moduri. Vom avea în total (n/p)! p moduri (modulo 100019).

Dacă n+1 este divizibil cu p, atunci vor exista câte n/p + 1 persoane și locuri care dau același rest nenul la împărțirea cu p și n/p persoane și locuri ce dau restul 0 la împărțirea cu p. Ca în cazul anterior vom avea în total (n/p +1)! p-1 * (n/p)! moduri (modulo 100019).

Answer 1

#include <iostream>
#include <math.h>
using namespace std;

long int factorial(int n){
long int i,fact=1;
for(i=2;i<=n;i++){
fact=fact*i;
}
return fact;
}
int main(){
long int n,p,i,k=1,r;
cout<<"Introduceti nr de persoane si divizorul:";
cin>>n>>p;
int v[n+1];
if(n%p==0){
cout<<(pow(n/p,p))%100019;
}
else if((n+1)%p==0){
cout<<(pow(n/p+1,p-1)*factorial(n/p))%100019;
}
else{
cout<<"Nu exista permutari care sa indeplineasca conditia!";
}
return 0;
}