Create a gist now

Instantly share code, notes, and snippets.

kangaroo.cpp
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define DBG(x) cout << #x << " = " << x << endl
typedef long long ll;
const ll MOD = 1000000007;
const int MAXN = 310;
int n;
int a[MAXN]; // 体の大きさ
int b[MAXN]; // ポケットの大きさ
int rightTo[MAXN+1]; // 各 P に対する Q の位置
ll fact[MAXN]; // fact[y] = y!
void doit(int from, int to, ll dp[MAXN][MAXN]) {
int len = to - from;
dp[0][0] = 1;
for (int i = 0 ; i < len ; i++) {
for (int u = 0 ; u < len ; u++) {
if (dp[i][u] == 0) {
continue;
}
ll base = dp[i][u];
ll choice = rightTo[to] - rightTo[to-1-i] - u;
dp[i+1][u] = (dp[i+1][u] + base) % MOD;
dp[i+1][u+1] = (dp[i+1][u+1] + base * choice % MOD) % MOD;
}
}
}
ll solve() {
fact[0] = 1;
for (int i = 1 ; i < MAXN ; i++) {
fact[i] = (fact[i-1] * i) % MOD;
}
for (int top = 0 ; top < n ; top++) {
int hoge = n;
for (int i = 0 ; i < n ; i++) {
if (a[top] < b[i]) {
hoge = i;
break;
}
}
rightTo[top] = hoge;
}
rightTo[n] = n;
ll sum = 0;
// top: 解説で言うところの P
for (int top = 0 ; top < n ; top++) {
// [0,P), [0,Q) 間の数え上げ。 dpLeft[右から数えてどこまで使った][いくつ使った]
ll dpLeft[MAXN][MAXN];
memset(dpLeft, 0, sizeof(dpLeft));
doit(0, top, dpLeft);
// [P+1,N), [Q,N) の数え上げ。 dpRight[右から数えてどこまで使った][いくつ使った]
ll dpRight[MAXN][MAXN];
memset(dpRight, 0, sizeof(dpRight));
doit(top+1, n, dpRight);
// 左右同数余らせた場合のみを数え上げ。j は解説で言うところの y
for (int j = 0 ; j <= top ; j++) {
int nokori = n - rightTo[top] - j;
if (nokori >= 0) {
ll add = dpLeft[top][top-j] * dpRight[n-1-top][nokori] % MOD * fact[j] % MOD;
sum += add;
}
}
}
return sum % MOD;
}
int main(int argc, char const *argv[]) {
cin >> n;
for (int i = 0; i < n ; i++) {
cin >> a[i] >> b[i];
}
sort(a, a+n);
sort(b, b+n);
cout << solve() << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment