Question

Un showroom din Strasbourg comercializează o gamă foarte mare de modele de autoturisme, aşezate pe n linii. Pe câte o linie se găsesc numai modele de autoturisme comercializate de acelaşi dealer. Un dealer poate avea modele pe mai multe linii. Parlamentul European doreşte să-şi înoiască parcul auto şi trimite responsabilul cu activitatea de transport la showroom pentru a se informa cu privire la variantele pe care le are pentru rezolvarea acestei probleme de achiziţie. Responsabilul trebuie să aleagă de la primul dealer f1f1 modele, de la al doilea dealer f2f2 modele, etc. Şirul de numere f1,f2,f3,…f1,f2,f3,… reprezintă termenii modulo k ai unei progresii aritmetice cu primul termen a şi raţia r. Dacă valoarea din şirul de numere este mai mare decât numărul de modele al dealerului corespunzător, atunci responsabilul nu mai alege nici un model al dealerului. Primul dealer este cel care are modelele pe prima linie şi, eventual, pe alte linii care urmează primei linii (dar nu neapărat consecutive!), al doilea dealer este cel care are modelele pe prima linie ce conţine modele diferite de cele ale primului dealer etc.

Cerința
Să se scrie un program care determină:

a) Numărul de dealeri prezenţi în showroom;
b) Numărul de modalităţi de achiziţie al modelelor de către Parlamentul European, modulo 9001.

Date de intrare
Fişierul de intrare showroom.in conţine pe prima linie numerele n, a, r, k separate prin exact un spaţiu, cu semnificaţia de mai sus, iar pe următoarele n linii se află denumirile modelelor din enunţ, separate prin unul sau mai multe spaţii. Fiecare linie se termină cu caracterul sfârşit de linie.

Date de ieșire
Fişierul de ieşire showroom.out va conţine pe prima linie numărul cerut la subpunctul a), iar pe a doua linie numărul cerut la subpunctul b).

Restricții și precizări
1 ≤ n ≤ 500;
1 ≤ a, r, k ≤ 10.000;
Denumirea unui model are cel mult 20 de litere mici şi/sau cifre;
Pe o linie sunt cel mult 100 de denumiri de modele şi nu pot exista mai mult de 10 spaţii între două modele;
Pot exista linii cu numerele de ordine i1,i2,…,ipi1,i2,…,ip cu modele ale aceluiaşi dealer, astfel încât perechile de linii (i1,i2),…,(ip−1,ip)(i1,i2),…,(ip−1,ip) au cel puțin un model de mașină în comun;
Pentru 60% din teste se garantează că valoarea k este mai mică sau egală decât 10.

Answer 1

#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <stack>
#include <list>

#include <numeric>
#include <algorithm>

#include <cstdio>
#include <fstream>
#include <iostream>
#include <sstream>
#include <iomanip>

#include <cctype>
#include <cmath>
#include <ctime>
#include <cassert>

using namespace std;

#define LL long long
#define PII pair <int, int>
#define VB vector <bool>
#define VI vector <int>
#define VD vector <double>
#define VS vector <string>
#define VPII vector <pair <int, int> >
#define VVI vector < VI >
#define VVB vector < VB >

#define FORN(i, n) for(int i = 0; i < (n); ++i)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define FORI(it, X) for(__typeof((X).begin()) it = (X).begin(); it !=(X).end(); ++it)
#define REPEAT do{
#define UNTIL(x) }while(!(x));

#define SZ size()
#define BG begin()
#define EN end()
#define CL clear()
#define X first
#define Y second
#define RS resize
#define PB push_back
#define MP make_pair
#define ALL(x) x.begin(), x.end()

#define IN_FILE "showroom.in"
#define OUT_FILE "showroom.out"

#define BASE 9001

ifstream fin(IN_FILE);
ofstream fout(OUT_FILE);

VVI lines, c;
int n, a, r, k, nrIDs;
map <string, int> id;
VI father, treeSize, companySizes, power;
VB isPrime;

void read()
{
nrIDs = 0;
fin >> n >> a >> r >> k;
lines.RS(n + 1);
FOR(i, 0, n)
{
string s;
getline(fin, s);

stringstream ss(s);
string model;
while (ss >> model)
{
if (!id.count(model))
{
++nrIDs;
id[model] = nrIDs;
}
lines[i].PB(id[model]);
}
}
fin.close();

}

int getRoot(int node)
{
if (father[node] == 0) return node;
return father[node] = getRoot(father[node]);
}

void unite(int node1, int node2)
{
node1 = getRoot(node1);
node2 = getRoot(node2);
if (node1 == node2) return;
if (treeSize[node1] > treeSize[node2])
{
father[node1] = node2;
treeSize[node2] += treeSize[node1];
}
else
{
father[node2] = node1;
treeSize[node1] += treeSize[node2];
}
}

void getCompanies()
{
father.RS(nrIDs + n + 1);
treeSize.RS(nrIDs + n + 1);
FOR(i, 1, n)
{
int thisRoot = nrIDs + i;
FORN(j, lines[i].SZ)
{
if (father[lines[i][j]] == 0)
{
father[lines[i][j]] = thisRoot;
++treeSize[thisRoot];
}
else
{
unite(thisRoot, lines[i][j]);
thisRoot = getRoot(thisRoot);
}
}
}

set <int> usedRoots;
FOR(i, 1, n)
{
int root = getRoot(lines[i][0]);
if (!usedRoots.count(root))
{
companySizes.PB(treeSize[root]);
usedRoots.insert(root);
}
}
}

void doErast(int limit)
{
isPrime.RS(limit + 1, true);
int outerLimit = sqrt(double(limit));
FOR(i, 2, outerLimit)
{
if (!isPrime[i]) continue;
for(int j = i + i; j <= limit; j += i) isPrime[j] = false;
}
}

void addPowers(int x)
{
int factor = 2;
while (!isPrime[x])
{
while ((x % factor) == 0)
{
++power[factor];
x /= factor;
}
++factor;
}
++power[x];
}

void subPowers(int x)
{
int factor = 2;
while (!isPrime[x])
{
while ((x % factor) == 0)
{
--power[factor];
x /= factor;
}
++factor;
}
--power[x];
}

int getComb(int nn, int kk)
{
power.CL, power.RS(nn + 1);
FOR(i, 2, nn) addPowers(i);
FOR(i, 2, kk) subPowers(i);
FOR(i, 2, nn - kk) subPowers(i);

int ans = 1;
FOR(i, 2, nn)
FORN(j, power[i]) ans = (ans * i) % BASE;
return ans;
}

int solve()
{
int solution = 1, f = a;
FORN(i, companySizes.SZ)
{
if (f <= companySizes[i]) solution = (solution * getComb(companySizes[i], f)) % BASE;
f = (f + r) % k;
}
return solution;
}

int main()
{
read();

//Solve
getCompanies();
doErast(*max_element(ALL(companySizes)));

//Write data
fout << companySizes.SZ << endl;
fout << solve();
fout.close();

return 0;
}