Planeetat

#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
const int M = 1e9+7;
// f(n, m): kuinka monta tapaa jakaa m solmua puiksi, joiden juuret on tietyt n solmua
// f(n, m) = n*(n+m)^(m-1)
// todistus:
// Indeksöidään solmujoukot |A| = n ja |B| = m, A1, ..., An ja B1, ..., Bm
// Samaan tapaan kuin todistuksessa sille, että puita on n^(n-2),
// kaikille paitsi B1 valitaan kaari mihin tahansa solmuun.
// Kombinaatioita on (n+m)^(m-1).
// Jokaista tälläistä vastaa n kappaletta haluttuja rakenteita (ei syklejä ja B1 lähtee kaari)
// seuraalla muunnoksella:
// Valitaan kaikki syklit, järjestetään ne niiden sisältämän pienimmän indeksin mukaan,
// ja tehdään polku, joka lähtee B1 ja etenee syklejä suurimmasta pienimpään.
// Sykliin mentäessä mennään aina ensin pienimpään indeksiin, kierretään se ympäri,
// ja korvataan viimeinen kaari sellaisella, joka menee seuraavaan sykliin.
// Polku loppuu johonkin A:n solmuun, ja tälle jää n vaihtoehtoa.
// Halutuista puurakenteista voi päätellä yksikäsitteisesti syklejä sisältävän esityksen
// tarkastelemalla polkua B1 -> ... -> Ai. Uusi sykli alkaa aina, kun indeksi on pienempi
// kuin mikään aiempi. Tieto viimeisestä solmusta Ai menetetään (jälleen n vaihtoehtoa),
// mutta kuvaus on muuten injektiivinen.
int f[N]; // f[x] = f(x, n-x)
// s(n, m, k) on sellaisten verkkojen määrä, jossa n solmua sykleissä, m muuta solmua ja k komponenttia.
// Saadaan kaava s(n, m, k) = nCr(n+m, n) * g(n, k) * f(n, m),
// missä g(n, k) on n:n solmun permutaatioiden määrä, joissa on k sykliä.
// g(n, k) löytyy rekursio
// g(n, k) = (n-1) * g(n-1, k) + g(n-1, k-1)
// (uusi solmu voidaan joko lisätä olemassaolevaan sykliin, minkä tahansa
//  n-1 solmun jälkeen, tai se voi muodostaa uuden syklin.)
int nCr[N][N];
int g[N][N];
long fpow(long b, long e) {
  if (e == 0) return 1;
  if (e%2) return fpow(b, e-1)*b%M;
  long t = fpow(b, e/2);
  return t*t%M;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 0; i < N; ++i) nCr[i][0] = 1;
  g[0][0] = 1;
  for (int i = 1; i < N; ++i) {
    for (int j = 1; j < N; ++j) {
      nCr[i][j] = (nCr[i-1][j] + nCr[i-1][j-1])%M;
      g[i][j] = (long(i-1)*g[i-1][j]%M + g[i-1][j-1])%M;
    }
  }
  int n;
  cin >> n;
  for (long x = 1; x < n; ++x) {
    f[x] = x*fpow(n, n-x-1)%M;
  }
  f[n] = 1;
  for (int k = 1; k <= n; ++k) {
    long res = 0;
    for (int x = 1; x <= n; ++x) {
      // s(x, n-x, k)
      res = (res + long(nCr[n][x])*g[x][k]%M*f[x])%M;
    }
    cout << res << "\n";
  }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: ACCEPTED

Test 12

Group: 2, 3

Verdict: ACCEPTED

Test 13

Group: 2, 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: ACCEPTED

Test 18

Group: 3

Verdict: ACCEPTED

Test 19

Group: 3

Verdict: ACCEPTED

Test 20

Group: 3

Verdict: ACCEPTED

Test 21

Group: 3

Verdict: ACCEPTED

Test 22

Group: 3

Verdict: ACCEPTED

Test 23

Group: 3

Verdict: ACCEPTED

Test 24

Group: 3

Verdict: ACCEPTED

Test 25

Group: 3

Verdict: ACCEPTED