第一问：
先不考虑山的高度有相同的：直接按照高度降序排序，试着将每一座山插入到前面山的缝隙中.
- 当然，这并不代表这些山的相对位置是固定的，因为后面高度更低的山是有机会插入进来的，所以就可以做到将所有情况都考虑到.
- 假设现在要插入第 $i$ 座山，前面已插入了 $i-1$ 座比当前山高的山，那么当前能插入的选择应该是 $min(key_{i},i)$ 种. (既然前面的山都高于第 $i$ 座，所以能且只能插入到这些位置上).
- 令 $f_{i}$ 表示从大到小插入了 $i$ 座山的方案数，则 $f_{i}=f_{i-1} imes min(key_{i},i)$
现在将高度相同的情况考虑进去：
- 如果像之前高度不同的做法取做的话高度相同的山会互相牵制.
- 为了不让这种情况发生，我们令高度相同的第 $i$ 座山的 $key$ 变为 $key+same(i)$，即加上一个在它之前和它高度相同的数量.
- 然而，这样做的话可能会出现非法情况，即可能会多出来一些.为了不让这种情况出现，我们在排序的时候高度相同的按照关键字从小到大排序.
第二问：
令 $f[i][j]$ 表示相同高度，排完序后编号为 $[l,r]$ 的山中，插进第 $i$ 个，且插入到所有山中 $j$ 位置前的方案数.
$i$ 有两种插入方式：
- 插到第 $j$ 座山的前面，则 $i-1$ 也需要插进前 $j$，故 $f[i-1][j]Rightarrow f[i][j]$.
- 插入到前 $j-1$ 座山里面，则直接调用 $f[i][j-1]$ 即可.
综上，$f[i][j]=f[i-1][j]+f[i][j-1]$，可以用滚动数组滚起来.
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1009
#define mod 2011
#define ll long long
#define setIO(s) freopen(s".in", "r" , stdin)
using namespace std;
int n ;
struct Node
{
int key, h;
}t[N];
bool cmp(Node a, Node b)
{
return a.h == b.h ? a.key < b.key : a.h > b.h;
}
namespace case1
{
int f[N], key[N], tmp[N];
int main()
{
int i ;
f[0] = 1;
for(i = 1; i <= n ; ++ i)
{
key[i] = t[i].key;
if(t[i].h == t[i - 1].h) key[i] += tmp[i - 1], tmp[i] = tmp[i - 1] + 1;
else tmp[i] = 1;
f[i] = (ll) (f[i - 1] * min(key[i], i)) % mod;
}
printf("%d ", f[n]);
return 0;
}
};
namespace case2
{
int f[N];
int main()
{
int i , j, k, pos, ans = 1;
for(i = 1 ; i <= n ; i = pos + 1)
{
pos = i;
while(pos < n && t[pos + 1].h == t[pos].h) ++ pos;
memset(f, 0, sizeof(f)), f[0] = 1;
for(j = i ; j <= pos ; ++ j)
for(k = 1 ; k <= min(i - 1, t[j].key - 1); ++ k)
f[k] = (f[k] + f[k - 1]) % mod;
int re = 0;
for(j = 0; j <= min(i - 1, t[pos].key - 1) ; ++ j) re = (re + f[j]) % mod;
ans = ans * re % mod;
}
printf("%d
", ans);
return 0;
}
};
int main()
{
// setIO("input");
int i , j;
scanf("%d", &n);
for(i = 1; i <= n ; ++ i)
scanf("%d%d", &t[i].h, &t[i].key);
sort(t + 1, t + 1 + n, cmp);
case1::main(), case2::main();
return 0;
}