Planeetat

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll M=1e9+7, bi[5050][5050], kertoma[5050], J[5050][5050], ans[5050];

ll pot(ll a, ll b){
    if (a==0) return 1;
    if (b==0) return 1;
    ll d=pot(a, b/2);
    d = (d*d)%M;
    if (b%2==0) return d;
    else return (d*a)%M;
}

ll bin(ll a, ll b){
    if (bi[a][b]) return bi[a][b];
    else{
        ll c=kertoma[a];
        c = (c*pot(kertoma[b], M-2))%M;
        c = (c*pot(kertoma[a-b], M-2))%M;
        bi[a][b]=c;
        return c;
    }
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin >> n;
    kertoma[0]=1;
    for (int i=1; i<=n; ++i) kertoma[i]=(kertoma[i-1]*i)%M;
    for (int i=1; i<=n; ++i) J[i][1]=kertoma[i-1];
    for (int i=2; i<=n; ++i){
        for (int j=2; j<=i; ++j){
            J[i][j]=(J[i-1][j]*(i-1)+J[i-1][j-1])%M;
        }
    }
    for (int i=1; i<=n; ++i){
        __int128_t a=0;
        for (int j=i; j<=n; ++j){
            if (j<n) a = (a + (__int128_t)J[j][i]*bin(n, j)*j * pot(n, n-j-1))%M;
            else a = (a + J[j][i]*bin(n, j))%M;
        }
        ans[i]=(ll)a;
    }
    for (int i=1; i<=n; ++i){
        cout << ans[i] << "\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: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 3

Verdict: TIME LIMIT EXCEEDED