1 条题解
-
0
狐狸 LV 7 @ 7 年前
注意memset别用多了, 超时啊..最好用滚动数组
- 1
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 2
- 已通过
- 1
- 通过率
- 50%
- 上传者
注意memset别用多了, 超时啊..最好用滚动数组
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MOD 2011
using namespace std;
const int N = 1000 + 10;
struct node {
int hi, key;
bool operator < (const node & b) const {
return hi != b.hi ? hi > b.hi : key < b.key;
}
} data[N];
int f[2][N];
int last[N];
int main() {
freopen("in.txt", "r", stdin);
int n;
while(scanf("%d", &n) != EOF) {
memset(last, 0, sizeof(last));
for (int i = 1; i <= n; i++)
scanf("%d %d", &data[i].hi, &data[i].key);
sort(data + 1, data + n + 1);
long long ans = 1ll;
int pos;
for (int i = 1; i <= n; i++) {
if (data[i].hi != data[i - 1].hi || i == 1) pos = i;
ans = (ans * min(i, data[i].key + i - pos)) % MOD;
last[i] = i - pos;
}
printf("%lld ", ans);
ans = 1;
for (int i = 1; i <= n; ) {
memset(f, 0, sizeof(f));
int l = i, r = n;
for (int j = i + 1; j <= n; j++) {
if (data[j].hi != data[j - 1].hi) {
r = j - 1;
break;
}
}
int o = 0;
for (int j = 1; j <= i; j++) {
if (j <= data[l].key) f[o][j] = 1;
f[o][j] = (f[o][j] + f[o][j - 1]) % MOD;
}
for (int j = l + 1; j <= r; j++) {
int now = last[j];
o ^= 1;
memset(f[o], 0, sizeof (f[o]));
for (int k = 1; k <= i; k++) {
if (k <= data[j].key) f[o][k] = (f[o][k] + f[o ^ 1][k]) % MOD;
f[o][k] = (f[o][k] + f[o][k - 1]) % MOD;
}
}
int res = f[o][min(data[r].key, i)];
ans = (1ll * res * ans) % MOD;
i = r + 1;
}
printf("%lld\n", ans);
}
return 0;
}