Submission #213321

#	Time	Username	Problem	Language	Result	Execution time	Memory
213321		quocnguyen1012	Zapina (COCI20_zapina)	C++14	110 / 110	173 ms	1400 KiB

zapina

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 355, mod = 1e9 + 7;

int f[maxn][maxn], C[maxn][maxn], N;

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  for(int i = 0; i < maxn; ++i)
    C[0][i] = 1, C[i][i] = 1;
  for(int i = 1; i < maxn; ++i){
    for(int j = i + 1; j < maxn; ++j)
      C[i][j] = (C[i - 1][j - 1] + C[i][j - 1]) % mod;
  }
  cin >> N;
  f[0][0] = 1;
  for(int i = 1; i <= N; ++i){
    for(int j = 0; j <= N; ++j){
      for(int k = 0; k <= j; ++k){
        if(k != i) f[i][j] = (f[i][j] + 1ll * C[k][N - j + k] * f[i - 1][j - k]) % mod;
      }
    }
  }
  ll res = 1;
  for(int i = 1; i <= N; ++i) res = res * N % mod;
  cout << (res - f[N][N] + mod) % mod;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55