# [JLOI2013] terrain generation

A classic method of permutation and counting is to insert elements into the sequence in a certain order. It is not difficult to find the first question of this question. In order to know how many in front of each position are larger than the current position, we can consider inserting mountains into the sequence from large to small according to the height. Assuming there is no mountain with the same height at present, it is currently considered to insert the \ (I \) mountain, \ ({a_i}{Val} \) is the keyword of the current mountain, then there are \ (\ min \ {I, {a_i}{Val} \) positions we can insert, which can be multiplied according to the multiplication principle. But now it's more difficult to deal with mountains with the same height. It's not difficult to find that the difficulty lies in that different insertion sequences may correspond to an arrangement, so our classic idea is to specify an insertion sequence so that it can generate all the arrangements. Therefore, we can find that every time we insert the mountain with the smallest keyword first, we can cover all situations, because the mountain with small keyword can also insert the mountain with large keyword behind the new position contributed by the mountain with small keyword, but not vice versa. Therefore, we rank the first keyword by height from large to small, and the second keyword by keyword from small to large. There are \ (\ min \ {I, {a_i}{Val} + cnt \} \) positions that can be inserted in each position, and \ (cnt \) is how many mountains with the same height before him. These numbers can be simply multiplied according to the multiplication principle.

Considering the second question, we can find that mountains with different heights will not affect the weight recording. Therefore, we only need to consider the scheme of each height and simply multiply it according to the multiplication principle. Next, we can find that in fact, the mountains with the same height are the same, so our problem can be transformed into \ (n \) unmarked energy seeking. Each energy seeking can be put into \ (1 \ SIM \ min \ {I, {a_i}{val} \} \) boxes to find the number of schemes. Because the ball is the same, we will remember if and only if some balls will exchange positions. Therefore, in order not to allow the ball to exchange positions, we decide that each time we put the ball, we must put it in the box where we put the ball last time and in the box after that, so that we won't remember again. Therefore, according to this method, we have a \ (DP \), let \ (DP {I, j} \) represent the scheme that the first \ (I \) ball is placed in the first \ (j \) box, then there is transfer \ (DP {I, j} = \ sum \ limits {k = 1} ^ j DP {I - 1, K} \), and find that this is a prefix sum form, so we press down the first dimension to get the transfer \ (DP {I} = DP {I - 1} + DP _i \), and pay attention to the initialization \ (i = 1 \), Because directly initializing \ (i = 0 \) will result in \ (dp_0 = 0 \) and illegal answers will be calculated later.

```#include<bits/stdc++.h>
using namespace std;
#define N 1000 + 5
#define Mod 2011
#define rep(i, l, r) for(int i = l; i <= r; ++i)
struct node{
int h, val;
}a[N];
int n, ans, S[N], fac[N], inv[N], dp[N];
char c; int x = 0, f = 1;
c = getchar();
while(c > '9' || c < '0'){ if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int Inc(int a, int b){
return (a += b) >= Mod ? a - Mod : a;
}
int Mul(int a, int b){
return a * b % Mod;
}
int Qpow(int a, int b){
int ans = 1;
while(b){
if(b & 1) ans = Mul(ans, a);
a = Mul(a, a), b >>= 1;
}
return ans;
}
bool cmp(node a, node b){
return a.h == b.h ? a.val < b.val : a.h > b.h;
}
int main(){
n = read(), ans = fac[0] = inv[0] = 1;
rep(i, 1, n) fac[i] = Mul(fac[i - 1], i), inv[i] = Qpow(fac[i], Mod - 2);
sort(a + 1, a + n + 1, cmp);
rep(i, 1, n){
int j = i, cnt = 0;
while(j <= n && a[j].h == a[i].h) ans = Mul(ans, min(i, a[j].val) + cnt), ++cnt, ++j;
i = j - 1;
}
printf("%d ", ans), ans = 1;
rep(i, 1, n){
int j = i + 1, tmp = 0; memset(dp, 0, sizeof(dp));
rep(k, 1, min(i, a[i].val)) dp[k] = 1;
while(j <= n && a[j].h == a[i].h){
rep(k, 1, min(i, a[j].val)) dp[k] = Inc(dp[k], dp[k - 1]);
++j;
}
rep(k, 1, min(i, a[j - 1].val)) tmp = Inc(tmp, dp[k]);
ans = Mul(ans, tmp);
i = j - 1;
}
printf("%d", ans);
return 0;
}
```

Tags: dp

Posted by Rhysyngsun on Wed, 25 May 2022 11:53:57 +0300