分析
很妙的思路。
把所有的山按高度从大到小排序,然后按顺序加进去。
显然高度相同的山关键值大的要放后面。所以还要以关键值为第二关键字排序。
第$i$座山能放的位置只有$c_i=\min\left\{k_i,i\right\}$种($k_i$为$i$的关键值)。
所以$ans1=\prod\limits_{i=1}^nc_i$。
考虑第二问怎么做。
假设$[l,r]$这段区间高度相同。设$f[i][j]$表示$[l,r]$中的前$i$座山,放在前$j$个位置的方案数。
显然有$\large f[i][j]=\sum\limits_{k=1}^{\min\{k_i,l\}-1}f[i-1][k]$。
稍微变一下就可以变成,$\large f[i][j]=f[i-1][j]+f[i][j-1]$。
然后还可以滚动掉第一维。
对于每一段区间$[l,r]$,它的答案是$\sum\limits_{i=0}^{\min\{k_r,l\}-1}f[i]$。
$ans2$就是每个区间答案的积。
代码
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=1000+10;
const int MOD=2011;
struct Mountain { int height,key; };
bool operator <(Mountain a,Mountain b) {
if (a.height!=b.height) return a.height>b.height;
else return a.key<b.key;
}
int n,ans1=1,ans2=1;
Mountain a[N];
int f[N];
int main() {
n=read();
for (re int i=1;i<=n;++i) a[i].height=read(),a[i].key=read();
sort(a+1,a+n+1); a[0].height=0x3f3f3f3f;
for (re int i=1,j=0;i<=n;++i) {
if (a[i].height<a[j].height) j=i;
ans1=ans1*(min(j,a[i].key)+i-j)%MOD;
}
for (re int i=1,pos;i<=n;++i) {
pos=i; while (a[i].height==a[pos].height&&pos<=n) ++pos;
--pos; memset(f,0,sizeof(f)); f[0]=1;
for (re int j=i;j<=pos;++j)
for (re int k=1;k<min(a[j].key,i);++k)
f[k]=(f[k]+f[k-1])%MOD;
int sum=0;
for (re int j=0;j<min(a[pos].key,i);++j)
sum=(sum+f[j])%MOD;
ans2=ans2*sum%MOD,i=pos;
}
printf("%d %d\n",ans1,ans2);
return 0;
}