Luogu

BZOJ

分析

很妙的思路。

把所有的山按高度从大到小排序，然后按顺序加进去。

显然高度相同的山关键值大的要放后面。所以还要以关键值为第二关键字排序。

第$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;
}