이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int MN = 505, LOG = 18, MOD = 1e9 + 7;
int dp[MN][MN<<1],pre[MN<<1][MN][2],a[MN],b[MN];
int ch[MN][MN], ch2[MN<<1][MN][2], iv[MN<<1];
int inv (int base) {
int res = 1, exp = MOD - 2;
while (exp) {
if (exp&1) res = (ll)res * base % MOD;
base = (ll)base * base % MOD;
exp>>=1;
}
return res;
}
int choose (int n, int k) {
assert(n >= 0 && k >= 0);
int res = 1;
for (int i = n; i > n-k; i--) res = (ll)res * i % MOD;
for (int i = 2; i <= k; i++) res = (ll)res * iv[i] % MOD;
return res;
}
int calc (int j, int x, bool ree) {
int ret = ch2[j][x-ree][ree];
for (int zeros = 1; zeros <= x-2; zeros++) ret = (ret + (ll)ch2[j][x-zeros-ree][ree] * ch[x-2][zeros]) % MOD;
return ret;
}
int main () {
int n;
scanf ("%d",&n);
for (int i = 0; i <= n*2; i++) iv[i] = inv(i);
for (int i = 0; i <= n; i++) for (int j = 0; j <= i; j++) ch[i][j] = choose(i,j);
vector<int> xs = {-1};
for (int i = 1; i <= n; i++) {
scanf ("%d %d",&a[i],&b[i]);
xs.push_back(a[i]); xs.push_back(b[i]);
}
sort(xs.begin(),xs.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end());
int m = xs.size() - 1;
for (int j = 1; j <= m; j++) {
ch2[j][0][0] = ch2[j][0][1] = 1;
for (int i = 1; i <= n; i++) {
ch2[j][i][0] = (ll)ch2[j][i-1][0] * (xs[j]-xs[j-1]-i+1) % MOD * inv(i) % MOD;
ch2[j][i][1] = (ll)ch2[j][i-1][1] * (xs[j]-xs[j-1]-i) % MOD * inv(i) % MOD;
}
}
for (int j = 1; j <= m; j++) {
for (int i = 1; i <= n; i++) {
pre[j][i][0] = calc(j,i,0);
pre[j][i][1] = calc(j,i,1);
}
}
for (int j = 0; j <= m; j++) dp[0][j] = 1;
for (int i = 1; i <= n; i++) {
//printf ("i %d\n",i);
for (int j = 0; j <= m; j++){
if (j) dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
if (xs[j] < a[i] || (j&&b[i] <= xs[j-1])) continue;
bool ree = a[i]==xs[j]; int cnt = 0;
for (int k = i; k >= 1; k--) { //everything before k was <= xs[j-1]
if (a[k] > xs[j] || b[k] <= xs[j-1] || (k!=i&&a[k]==xs[j])) continue;
++cnt;
dp[i][j] = (dp[i][j] + (ll)dp[k-1][j-1] * pre[j][cnt][ree]) % MOD;
}
}
for (int j = 0; j <= m; j++) {
dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
//printf ("dp[%d][%d] = %d\n",i,j,dp[i][j]);
}
}
printf ("%d\n",(dp[n][m] + MOD - 1) % MOD);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
boat.cpp: In function 'int main()':
boat.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d",&n);
~~~~~~^~~~~~~~~
boat.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d",&a[i],&b[i]);
~~~~~~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |