제출 #220243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
220243		rama_pang	Tents (JOI18_tents)	C++14	100 / 100	239 ms	35712 KiB

tents

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

const int MOD = 1e9 + 7;
const int INV2 = (MOD + 1) / 2; // modular inverse of 2

int ADD() { return 0; }
int MUL() { return 1; }

template<typename... Tail>
int ADD(int Head, Tail... T) {
  return (Head += ADD(T...)) >= MOD ? Head - MOD : Head;
}

template<typename... Tail>
int MUL(int Head, Tail... T) {
  return 1ll * Head * MUL(T...) % MOD;
}

template<typename... Tail>
void RADD(int &Head, Tail... T) {
  Head = ADD(Head, T...);
}

int PartialSolutionDP(int N, int M) { // solution in O(N^3)
  vector<vector<int>> dp, nxt_dp;
  dp = nxt_dp = vector<vector<int>>(M + 2, vector<int>(M + 2, 0)); // [free_column][unmatched_tent]
  dp[M][0] = 1;

  for (int row = 0; row < N; row++) {
    for (int free_column = 0; free_column <= M; free_column++) {
      for (int unmatched_tent = 0; unmatched_tent <= M; unmatched_tent++) {
        int cur = dp[free_column][unmatched_tent];

        // place 2 tents
        if (free_column >= 2) {
          RADD(nxt_dp[free_column - 2][unmatched_tent], MUL(free_column, free_column - 1, cur, INV2));
        }

        // place 1 tent by itself
        if (free_column >= 1) {
          RADD(nxt_dp[free_column - 1][unmatched_tent + 1], MUL(free_column, cur));
        }

        // place 1 tent adjacent to an unmatched tent
        if (unmatched_tent >= 1) {
          RADD(nxt_dp[free_column][unmatched_tent - 1], MUL(unmatched_tent, cur));
        }

        // place no tents
        RADD(nxt_dp[free_column][unmatched_tent], cur);
      }
    }

    swap(dp, nxt_dp);
    nxt_dp = vector<vector<int>>(M + 1, vector<int>(M + 1, 0));
  }

  vector<int> POW4(M + 1);
  POW4[0] = 1;
  for (int i = 1; i <= M; i++) {
    POW4[i] = MUL(POW4[i - 1], 4);
  }

  int res = 0;
  for (int free_column = 0; free_column <= M; free_column++) {
    for (int unmatched_tent = 0; unmatched_tent <= M; unmatched_tent++) {
      RADD(res, MUL(POW4[unmatched_tent], dp[free_column][unmatched_tent])); // each unmatched tent can be placd in 4 directions
    }
  }

  return (res - 1 + MOD) % MOD; // decrease 1 (the empty grid placement)
}

int Solve(int N, int M) { // full solution in O(N^2)
  vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0)); // dp[current_row][free_column]

  dp[N][M] = 1;
  for (int row = N; row > 0; row--) {
    for (int free_column = 0; free_column <= M; free_column++) {
      // Place 0 tent.
      RADD(dp[row - 1][free_column], dp[row][free_column]);

      // Place 1 tent in the current row, there are 4 * free_column ways to do it.
      if (free_column >= 1) {
        RADD(dp[row - 1][free_column - 1], MUL(free_column, 4, dp[row][free_column]));
      }

      // Place 2 tents with the same row, there are col * (col - 1) / 2 ways to do it. 
      // Afterwards, the number of free columns decreased by 2.
      if (free_column >= 2) {
        RADD(dp[row - 1][free_column - 2], MUL(free_column, free_column - 1, dp[row][free_column], INV2));
      }

      // Place 2 tents with the same column, where one of them is in the current row.
      // Afterwards, there exists a row later on where we cannot place anything, so
      // we can safely assume it is not there. There are free_col ways to choose a column,
      // and N - 1 ways to pick the other pair (the row must be yet to be processed).
      if (row >= 2 && free_column >= 1) {
        RADD(dp[row - 2][free_column - 1], MUL(free_column, row - 1, dp[row][free_column]));
      }
    }
  }

  int res = 0;
  for (int col = 0; col <= M; col++) {
    RADD(res, dp[0][col]);
  }

  return (res - 1 + MOD) % MOD; // decrease 1 for empty grid configuration
}

int main() {
  int N, M;
  cin >> N >> M;
  cout << Solve(N, M) << "\n";
  return 0;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52