Planeetat

input/code.cpp: In function 'std::vector<int> mull(const std::vector<int>&, const std::vector<int>&, const FFT_mod&)':
input/code.cpp:62:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < left.size(); i++) {
                    ~~^~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:250:8: warning: unused variable 'lol2' [-Wunused-variable]
     ll lol2[100];
        ^~~~

#include <bits/stdc++.h>
#include <vector>
#include <utility>
#include <stdio.h>
using namespace std;
 
typedef long long ll;

ll M = 1e9 + 7;
ll ans[10101];
ll lol[10101];
ll fact[10101];
ll dp[5005][5005];
ll pot[5005][5005];
ll modinv[5005];
ll modinvfact[5005];
ll ncr[5005][5005];

template <typename T>
T extGcd(T a, T b, T& x, T& y) {
   if (b == 0) {
      x = 1;
      y = 0;
      return a;
   }
   else {
      int g = extGcd(b, a % b, y, x);
      y -= a / b * x;
      return g;
   }
}

template <typename T>
T modInv(T a, T m) {
   T x, y;
   extGcd(a, m, x, y);
   return (x % m + m) % m;
}

long long crt(const std::vector< std::pair<int, int> >& pp, int mod = -1);


#include <algorithm>


struct FFT_mod {
   int mod, root, root_1, root_pw;
};

extern FFT_mod suggested_fft_mods[5];
void ntt_shortmod(std::vector<int>& a, bool invert, const FFT_mod& mod_data);


const int mod = 1000000007;

vector<int> mull(const vector<int>& left, const vector<int>& right, const FFT_mod& mod_data) {
   vector<int> left1 = left, right1 = right;
   ntt_shortmod(left1, false, mod_data);
   ntt_shortmod(right1, false, mod_data);

   for (int i = 0; i < left.size(); i++) {
      left1[i] = (left1[i] * 1ll * right1[i]) % mod_data.mod;
   }

   ntt_shortmod(left1, true, mod_data);
   return left1;
}


vector<int> mult(vector<int>& left, vector<int>& right) {
   int ssss = left.size() + right.size() - 1;
   int pot2;
   for (pot2 = 1; pot2 < ssss; pot2 <<= 1);

   left.resize(pot2);
   right.resize(pot2);

   vector<int> res[3];
   for (int i = 0; i < 3; i++) {
      res[i] = mull(left, right, suggested_fft_mods[i]);
   }

   vector<int> ret(pot2);
   for (int i = 0; i < pot2; i++) {
      vector< pair<int,int> > mod_results;
      for (int j = 0; j < 3; j++) {
         mod_results.emplace_back(res[j][i], suggested_fft_mods[j].mod);
      }
      ret[i] = crt(mod_results, mod);
   }
   return ret;
}

long long crt(const std::vector< std::pair<int, int> >& a, int mod) {
   long long res = 0;
   long long mult = 1;

   int SZ = a.size();
   std::vector<int> x(SZ);
   for (int i = 0; i<SZ; ++i) {
      x[i] = a[i].first;
      for (int j = 0; j<i; ++j) {
         long long cur = (x[i] - x[j]) * 1ll * modInv(a[j].second,a[i].second);
         x[i] = (int)(cur % a[i].second);
         if (x[i] < 0) x[i] += a[i].second;
      }
      res = (res + mult * 1ll * x[i]);
      mult = (mult * 1ll * a[i].second);
      if (mod != -1) {
         res %= mod;
         mult %= mod;
      }
   }

   return res;
}


FFT_mod suggested_fft_mods[] = {
   { 7340033, 5, 4404020, 1 << 20 },
   { 415236097, 73362476, 247718523, 1<<22 },
   { 463470593, 428228038, 182429, 1<<21},
   { 998244353, 15311432, 469870224, 1 << 23 },
   { 918552577, 86995699, 324602258, 1 << 22 }
};

int FFT_w[1050000];
int FFT_w_dash[1050000];


void ntt_shortmod(std::vector<int>& a, bool invert, const FFT_mod& mod_data) {
   // only use if mod < 5*10^8
   int n = (int)a.size();
   int mod = mod_data.mod;

   for (int i = 1, j = 0; i<n; ++i) {
      int bit = n >> 1;
      for (; j >= bit; bit >>= 1)
         j -= bit;
      j += bit;
      if (i < j)
         std::swap(a[i], a[j]);
   }

   for (int len = 2; len <= n; len <<= 1) {
      int wlen = invert ? mod_data.root_1 : mod_data.root;
      for (int i = len; i<mod_data.root_pw; i <<= 1)
         wlen = int(wlen * 1ll * wlen % mod_data.mod);

      long long tt = wlen;
      for (int i = 1; i < len / 2; i++) {
         FFT_w[i] = tt;
         FFT_w_dash[i] = (tt << 31) / mod;
         int q = (FFT_w_dash[1] * 1ll * tt) >> 31;
         tt = (wlen * 1ll * tt - q * 1ll * mod) & ((1LL << 31) - 1);
         if (tt >= mod) tt -= mod;
      }
      for (int i = 0; i<n; i += len) {
         int uu = a[i], vv = a[i + len / 2] % mod;
         if (uu >= 2*mod) uu -= 2*mod;
         a[i] = uu + vv;
         a[i + len / 2] = uu - vv + 2 * mod;

         for (int j = 1; j<len / 2; ++j) {
            int u = a[i + j];
            if (u >= 2*mod) u -= 2*mod;
            int q = (FFT_w_dash[j] * 1ll * a[i + j + len / 2]) >> 31;
            int v = (FFT_w[j] * 1ll * a[i + j + len / 2] - q * 1ll * mod) & ((1LL << 31) - 1);
            a[i + j] = u + v;
            a[i + j + len / 2] = u - v + 2*mod;
         }
      }
   }
   if (invert) {
      int nrev = modInv(n, mod);
      for (int i = 0; i<n; ++i)
         a[i] = int(a[i] * 1ll * nrev % mod);
   }
}

ll binpow(ll a, ll b, ll m) {
    if (b == -1) return binpow(a,M-2,M);
    ll ans = 1;
    while (b > 0) {
        if (b&1) ans = ans*a%m;
        a = a*a%m;
        b >>= 1;
    }
    return ans;
}

ll nCr(ll n, ll k) {
    ll ans = fact[n];
    ans *= binpow(fact[k], M-2, M);
    ans %= M;
    ans *= binpow(fact[n-k], M-2, M);
    ans %= M;
    return ans;
}

void preCalcFact(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i-1]*i;
        fact[i] %= M;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    preCalcFact(n);
    //preCalcPot:
    for (int i = 1; i <= n; i++) {
        pot[i][0] = 1;
        for (int j = 1; j <= n; j++) {
            pot[i][j] = pot[i][j-1]*i;
            if (pot[i][j] >= M) pot[i][j] %= M;
        }
    }
    //preCalcModInv:
    for (int i = 1; i <= n; i++) {
        modinv[i] = binpow(i,M-2,M);
    }
    //preCaclModInvFact:
    for (int i = 1; i <= n; i++) {
        modinvfact[i] = binpow(fact[i],M-2,M);
    }
    modinvfact[0] = 1;
    //preCalcNcr:
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            if (i == j) {
                ncr[i][j] = 1;
                continue;
            }
            ll ans = fact[i];
            ans *= modinvfact[j];
            if (ans >= M) ans %= M;
            ans *= modinvfact[i-j];
            if (ans >= M) ans %= M;
            ncr[i][j] = ans;
        }
    }
    
    ll lol2[100];
    for (int i = 1; i <= n; i++) {
        for (int j = 1 ; j <= i; j++) {
            //lol[i] += ((nCr(i,j)*fact[j])%M)*binpow(i,i-j-1,M);
            if (i-j-1 >= 0) {
                lol[i] += ((ncr[i][j]*fact[j])%M)*pot[i][i-j-1];
            } else {
                lol[i] += ((ncr[i][j]*fact[j])%M)*modinv[i];
            }
            if (lol[i] >= M) lol[i] %= M;
            /*
            ll x = ((nCr(i,j)*fact[j])%M)*binpow(i,i-j-1,M);
            lol2[i] += x;
            lol2[i] %= M;
            if (lol2[i] != lol[i]) {
                cout << "ERROR!" << endl;
                cout << "i: " << i << "j: " << j << endl;
                cout << pot[i][i-j-1] << endl;
                cout << ((ncr[i][j]*fact[j])%M)*pot[i][i-j-1] << endl;
                cout << x << endl;
                exit(0);
            }
            
            if (ncr[i][j] != nCr(i,j)) {
                cout << "ERROR!" << endl;
                cout << "i: " << i << "j: " << j << endl;
                cout << ncr[i][j] << " " << nCr(i,j) << endl;
                exit(0);
            }
            */
            //cout << "i: " << i << "j: " << j << endl;
            //cout << ncr[i][j] << " " << nCr(i,j) << endl;
            //cout << binpow(i, i-j-1,M) << " " << pot[i][i-j-1] << endl;
        }
    }
    dp[0][0] = 1;
    
    for (int i = 1; i <= n; i++) dp[i][1] = lol[i];
    for (int j = 2; j <= n; j++) {
        vector<int> f,g;
        for (int k = 1; k <= n-j+1; k++) {
            //f.push_back((binpow(fact[k-1],M-2,M)*lol[k])%M);
            //g.push_back((dp[j-2+k][j-1]*binpow(fact[j-2+k],M-2,M))%M);
            ll val = modinvfact[k-1]*lol[k];
            if (val >= M) val %=M;
            f.push_back(val);
            val = dp[j-2+k][j-1]*modinvfact[j-2+k];
            if (val >= M) val %= M;
            g.push_back(val);
        }
        auto p = mult(f,g);
        for (int i = j; i <= n; i++) dp[i][j] = (((ll)p[i-j])*fact[i-1])%M;
        /*
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                cout << dp[a][b] << " ";
            }
            cout << endl;
        }
        cout << endl;
        */
    }
    for (int i = 1; i <= n; i++) cout << dp[n][i] << "\n";
    
    //for (int i = 1; i <= n; i++) cout << lol[i] << " ";
    //cout << endl;
}

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