Submission #217348

#	Time	Username	Problem	Language	Result	Execution time	Memory
217348		rama_pang	Ruins 3 (JOI20_ruins3)	C++14	100 / 100	1939 ms	14456 KiB

ruins3

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

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

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

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

const int MAXN = 1205;

int N;
int A[MAXN];
bool is_special[MAXN];

int C[MAXN][MAXN]; // binomial coefficent
int ways[MAXN][MAXN];
int total_ways[MAXN];
int dp[MAXN][MAXN];

void Read() {
  cin >> N;
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
    is_special[A[i]] = true;
  }
}

void InitBinomial() {
  C[0][0] = 1;
  for (int i = 1; i <= 2 * N; i++) {
    for (int j = 0; j <= i; j++) {
      C[i][j] = ADD(C[i - 1][j], (j > 0 ? C[i - 1][j - 1] : 0));
    }
  }
}

void CountWays() {
  for (int l = 1; l <= N; l++) {
    // ways[i][j] = number of ways of choosing and permuting j integers from the set {1, 1, 2, 2, ..., i, i} 
    // (each element appears twice), such that the first element is l, and the following holds: p[i] >= i if 
    // we sort p, where p is the permutation chosen.
    
    ways[0][1] = 2; // the element l is already in the front of the set, of which there are two kinds

    for (int i = 1; i <= N; i++) { // we consider placing element i into the set
      for (int j = 0; j <= i; j++) { // the number of elements that we have picked. 
        // Note that i >= j always holds, and since j is the current position index and i is the element, 
        // p[i] >= i holds when sorted.

        ways[i][j] = 0; // reset

        if (i == l) {
          ways[i][j] = ADD(ways[i][j], ways[i - 1][j]); // we place element l into the front, of which there remains only one kind
          if (j >= 1) {
            ways[i][j] = ADD(ways[i][j], MUL(ways[i - 1][j - 1], j - 1)); // we place one of element l in one of the gaps
          }
        } else {
          ways[i][j] = ADD(ways[i][j], ways[i - 1][j]); // we do not place element i into the set
          if (j >= 1) {
            // We place a single element i into the set. Since we consider two pillars with height i different, 
            // we multiply it by 2. We can place the new element to j positions relative to the elements currently 
            // inside (ways[i - 1] have j - 1 elements, and there are j gaps between these elements that we can 
            // place the new element into). However, because we have already placed element l in the front, we cannot
            // place i in the front, so the possible gaps decrease by 1.
            ways[i][j] = ADD(ways[i][j], MUL(2, ways[i - 1][j - 1], j - 1));
          }
          if (j >= 2)  {
            ways[i][j] = ADD(ways[i][j], MUL(ways[i - 1][j - 2], j - 2, 2)); // we place both elements in the same gap. We can permute the new elements by 2!, so we multiply it by 2.
            ways[i][j] = ADD(ways[i][j], MUL(ways[i - 1][j - 2], j - 2, j - 3)); // we place both elements in different gaps
          }
        }
      }
    }

    for (int i = l; i <= N; i++) {
      total_ways[i] = ADD(total_ways[i], ways[i][i]); // ways[l][k][k] contributes to total_ways[k], since total_ways[k] = sum of ways[l][k][k] for l = 1, 2, ..., k.
    }
  }
}

void CalculateDP() {
  dp[2 * N][0] = 1; // dp[pos][height] = we have placed special pillars of height 1, 2, 3, ..., height and all pillars pos + 1, pos + 2, ..., 2N
  int special = 0, non_special = 0; // count special and non-special positions that we have encountered
  for (int pos = 2 * N; pos >= 1; pos--) {
    if (is_special[pos]) { // now current pillar is special
      for (int new_height = 0; new_height <= N; new_height++) { // new bound
        dp[pos - 1][new_height] = ADD(dp[pos - 1][new_height], dp[pos][new_height]); // we leave the current special pillar slot unfilled
        for (int cur_height = 0; cur_height < min(new_height, special + 1); cur_height++) { 
          // we fill the special pillar slot, and since we have filled exactly cur_height special positions, there are 
          // special - cur_height positions left. Since we add (add) new special pillars, and one of them must be at 
          // current position, we multiply it by C[special - cur_height][add - 1].
          int add = new_height - cur_height;
          dp[pos - 1][new_height] = ADD(dp[pos - 1][new_height], MUL(dp[pos][cur_height], C[special - cur_height][add - 1], total_ways[add])); 
          // we place a special pillar of height cur_height + 1 at the current position, to avoid double counting. 
          // The number of ways to achieve this is total_ways[add] = for all l = 1...add, if we place l at the front, 
          // how many ways are there to get a valid sequence that after earthqueakes, elements 1, 2, ..., add are left, 
          // such that the first element is 1? Since the final height of the first element is 1, it corresponds to
          // the final height of the pillar at the current position as cur_hegiht + 1 (since we are adding pillars with
          // height cur_height + 1, cur_height + 2, ..., final_height).
        }
      }
      special++;
    } else { // current pillar is not special
      for (int j = non_special; j <= special; j++) {
        // we have (j - non_special) pillars we can add without breaking rules (since adding a pillar of new height means 
        // that pillar must be special (and this location is not), we cannot place a new height).
        dp[pos - 1][j] = MUL(dp[pos][j], j - non_special); 
      }
      non_special++;
    }
  }
}

int Answer() {
  int res = dp[0][N];
  for (int i = 0; i < N; i++) {
    if (res & 1) res += MOD;
    res /= 2; // we previoiusly considered 2 pillars with the same height different, but in actuality they are the same. Thus we divide everything by 2^N
  }

  return res;
}

int main() {
  Read();
  
  InitBinomial();
  CountWays();
  CalculateDP();
  
  cout << Answer() << "\n";
  return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 52 / 52
• Subtask 3: 42 / 42