# PBinfo #4566 – Turism1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Alex, un mare entuziast al turismului, a decis să-și transforme pasiunea într-o afacere și să organizeze tururi ale orașului Bistrița. Orașul poate fi reprezentat ca un graf orientat al obiectivelor turistice, conectate direct de străzi. Totuși, dat fiind că abilitatea de a se orienta a lui Alex nu este comparabilă cu entuziasmul lui, organizarea traseelor este dificilă pentru el. În primul rând, el vrea să numere câte astfel de trasee există în oraș. Un traseu reprezintă o listă ordonată \(a\) de \(k\) obiective turistice, cu următoarele proprietăți:


De la nodul \( {a}_{i} \) se poate ajunge în nodul \( {a}_{i+1} \)
De la nodul \( {a}_{k} \) se poate ajunge în nodul \( {a}_{1} \)

Spunem că se poate ajunge de la nodul x la nodul y dacă există un drum de 0 sau mai multe străzi care începe în nodul x și se termină în nodul y. Există 2 tipuri de trasee turistice:


Tipul 1, în care obiectivele se pot repeta
Tipul 2, în care obiectivele trebuie să fie distincte

Graful obiectivelor turistice este un graf orientat în care o muchie de la x la y reprezintă un drum direct de la nodul x la nodul y. Alex are nevoie de ajutorul vostru, pentru a determina câte trasee de lungime k există pentru un tip dat de trasee turistice (Tipul 1 sau Tipul 2), pentru fiecare k de la 1 la Q.

Date de intrare
Prima linie conține T, tipul traseului.

A doua linie conține N, M și Q, reprezentând numărul de noduri și de muchii ale grafului, respectiv k-ul maxim pentru care Alex vrea să afle numărul de trasee. Următoarele M linii conțin câte 2 numere x, y, reprezentând o muchie orientată de la x la y.

Date de ieșire
Pentru fiecare linie k, de la 1 la Q, se va afișa numărul de trasee de lungime k, modulo \( 10^9+7 \).

Restricții și precizări

1 ≤ N ≤ 300 000
1 ≤ M, Q ≤ 1 000 000

Punctare

Pentru 7 puncte, T = 1, 1 ≤ N ≤ 6, 1 ≤ M ≤ 30, 1 ≤ Q ≤ 30.
Pentru alte 15 puncte, T = 1, 1 ≤ N, Q ≤ 50, 1 ≤ M ≤ 100.
Pentru alte 17 puncte, T = 1, 1 ≤ N, Q ≤ 1000, 1 ≤ M ≤ 2000.
Pentru alte 21 de puncte, T = 1, 1 ≤ N, Q ≤ 100 000, 1 ≤ M ≤ 200 000.
Pentru alte 8 puncte, T = 2, 1 ≤ N, Q ≤ 1000, 1 ≤ M ≤ 2000.
Pentru alte 20 de puncte, T = 2, 1 ≤ N, Q ≤ 100 000, 1 ≤ M ≤ 200 000.
Pentru restul de 12 puncte, T = 2, 1 ≤ N ≤ 300 000, 1 ≤ M, Q ≤ 1 000 000.

Exemplu 1:
turism.in

1
3 2 3
1 2
2 1
turism.out

3
5
9
Exemplu 2:
turism.in

2
3 2 3
1 2
2 1
turism.out

3
2
0
Exemplu 3:
turism.in

1
5 4 10
1 2
2 3
3 1
3 4
turism.out

5
11
29
83
245
731
2189
6563
19685
59051
Exemplu 4:
turism.in

2
6 7 4
1 2
2 3
3 4
4 5
5 3
3 1
3 6
turism.out

6
20
60
120
Exemplu 5:
turism.in

1
8 9 15
1 2
2 3
3 4
2 1
4 5
5 6
6 7
7 8
8 2
turism.out

8
64
512
4096
32768
262144
2097152
16777216
134217728
73741817
589934536
719476260
755810045
46480318
371842544
Explicații
Pentru primul exemplu, traseele sunt:


(1), (2), (3) – lungime 1
(1, 1), (1, 2), (2, 1), (2, 2), (3, 3) – lungime 2
(1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (1, 2, 2), (2, 1, 2), (2, 2, 1), (2, 2, 2), (3, 3, 3) – lungime 3

Pentru al doilea exemplu, traseele sunt:


(1), (2), (3) – lungime 1
(1, 2), (2, 1) – lungime 2

## Cod sursă C++

```cpp
// rapeanu.cpp
#include <bits/stdc++.h>
using namespace std;
ifstream fin("turism.in");
ofstream fout("turism.out");
const int MOD = 1e9 + 7;
int add(int a, int b) {
  a += b;
  if(a >= MOD) {
    a -= MOD;
  }
  return a;
}
int sub(int a, int b) {
  a -= b;
  if(a < 0) {
    a += MOD;
  }
  return a;
}
int mult(int a, int b) {
  return 1LL * a * b % MOD;
}
int lgpow(int b, int e) {
  int p = 1;
  while(e) {
    if(e & 1) {
      p = mult(p, b);
    }
    b = mult(b, b);
    e >>= 1;
  }
  return p;
}
void dfs(int nod, const vector<vector<int>> &graph, vector<int> &low, vector<int> &id, vector<int>& node_stack, vector<bool>& in_stack, int &last_id, function<void(int)> &callback) {
  low[nod] = id[nod] = ++last_id;
  node_stack.push_back(nod);
  in_stack[nod] = true;
  for(auto it: graph[nod]) {
    if(id[it] == 0){
      dfs(it, graph, low, id, node_stack, in_stack, last_id, callback);
    }
    if(in_stack[it]) {
      low[nod] = min(low[nod], low[it]);
    }
  }
  if(low[nod] == id[nod]) {
    int node_count = 0;
    while(in_stack[nod]){
      node_count++;
      in_stack[node_stack.back()] = false;
      node_stack.pop_back();
    }
    callback(node_count);
  }
}
int main() {
  int t;
  fin >> t;
  int n, m, q;
  fin >> n >> m >> q;
  vector<vector<int> > graph(n + 1, vector<int>());
  for(int i = 1;i <= m;i++) {
    int x, y;
    fin >> x >> y;
    graph[x].push_back(y);
  }
  vector<int> fact(max(n, q) + 1, 1);
  vector<int> ifact(max(n, q) + 1, 1);
  for(int i = 1;i <= n;i++) {
    fact[i] = mult(fact[i - 1], i);
  }
  ifact[n] = lgpow(fact[n], MOD - 2);
  for(int i = n - 1;i >= 0;i--) {
    ifact[i] = mult(ifact[i + 1], i + 1);
  }
  auto arang = [&fact, &ifact](int n, int k) {
    if(n < k) {
      return 0;
    }
    return mult(fact[n], ifact[n - k]);
  };
  vector<int> answer(q + 1, 0);
  vector<int> fr(n + 1, 0);
  function<void(int)> strat1 = [&fr, q](int n) {
    fr[n]++;
  };
  function<void(int)> strat2 = [&answer, q, &arang](int n) {
    for(int i = 1;i <= n;i++) {
      answer[i] = add(answer[i], arang(n, i));
    }
  };
  vector<int> id(n + 1, 0);
  vector<int> low(n + 1, 0);
  vector<int> node_stack(n + 1, 0);
  vector<bool> in_stack(n + 1, 0);
  int last_id = 0;
  for(int i = 1;i <= n;i++) {
    if(id[i] == 0) {
      dfs(i, graph, low, id, node_stack, in_stack, last_id, (t == 1 ? strat1:strat2));
    }
  }
  for(int i = 1;i <= n;i++) {
    if(!fr[i])continue;
    int current = 1;
    for(int j = 1;j <= q;j++){
      current = mult(current, i);
      answer[j] = add(answer[j], mult(fr[i], current));
    }
  }
  for(int i = 1;i <= q;i++) {
    fout << answer[i] << "\n";
  }
  return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4566)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4566/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4566/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)