제출 #447160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447160		bi11a1	Zapina (COCI20_zapina)	C++17	110 / 110	508 ms	3308 KiB

zapina

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

const ll mod = 1e9+7;
const ll MX = 351;

ll n;
ll dp[MX][MX][2], nr_dp[MX][MX];

ll nCr(ll N, ll R) {
  if (R == 1) return N;
  if (N == R || R == 0) return 1;
  ll &res = nr_dp[N][R];
  if (res != -1) return res;
  res = nCr(N-1, R) + nCr(N-1, R-1);
  res %= mod;
  return res;
}

ll Calc(ll pos, ll rem, bool happy) {
  if (pos > n) {
    return (happy && rem == 0);
  }
  ll &res = dp[pos][rem][happy];
  if (res != -1) return res;
  res = 0;
  for (ll i = 0; i <= rem; ++i) {
    res += nCr(rem, i) * Calc(pos+1, rem-i, happy | (pos==i));
    res %= mod;
  }
  return res;
}

int main() {
  memset(dp, -1, sizeof dp);
  memset(nr_dp, -1, sizeof nr_dp);
  cin >> n;
  cout << Calc(1, n, 0) << endl;
}

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