제출 #217348

#제출 시각아이디문제언어결과실행 시간메모리
217348rama_pang유적 3 (JOI20_ruins3)C++14
100 / 100
1939 ms14456 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...