#include<stdio.h>
#define mod 1000000007
typedef long long lld;
int n, m, r, a[270], b[270];
lld dy1[270][270], dy2[270][270], dap=1;
void countk(int k){
int i, j;
lld u, d1, d2;
dy1[0][0]=dy2[0][0]=1;
for(i=1; i<=n; i++){
if(b[i]<k)d1=d2=b[i]-a[i]+1, u=0;
else if(a[i]>k)u=b[i]-a[i]+1, d1=d2=0;
else d1=k-a[i]+1, d2=k-a[i], u=b[i]-k;
for(j=0; j<=i; j++){
dy1[i][j] = d1*dy1[i-1][j], dy2[i][j] = d2*dy2[i-1][j];
if(j)dy1[i][j] += u*dy1[i-1][j-1], dy2[i][j] += u*dy2[i-1][j-1];
dy1[i][j] %= mod, dy2[i][j] %= mod;
}
}
dap -= (dy1[n][r-1]-dy2[n][r-1]);
dap %= mod;
if(dap<0)dap += mod;
}
int main(){
int i;
scanf("%d%d", &n, &m);
for(i=1; i<=n; i++)scanf("%d%d", &a[i], &b[i]), dap=dap*(b[i]-a[i]+1)%mod;
scanf("%d", &r);
for(i=0; i<=m; i++)countk(i);
printf("%lld", dap);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
2228 KB |
Output is correct |
2 |
Correct |
0 ms |
2228 KB |
Output is correct |
3 |
Correct |
0 ms |
2228 KB |
Output is correct |
4 |
Correct |
0 ms |
2228 KB |
Output is correct |
5 |
Correct |
0 ms |
2228 KB |
Output is correct |
6 |
Correct |
0 ms |
2228 KB |
Output is correct |
7 |
Correct |
0 ms |
2228 KB |
Output is correct |
8 |
Correct |
0 ms |
2228 KB |
Output is correct |
9 |
Correct |
0 ms |
2228 KB |
Output is correct |
10 |
Correct |
0 ms |
2228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
2228 KB |
Output is correct |
2 |
Correct |
0 ms |
2228 KB |
Output is correct |
3 |
Correct |
0 ms |
2228 KB |
Output is correct |
4 |
Correct |
0 ms |
2228 KB |
Output is correct |
5 |
Correct |
0 ms |
2228 KB |
Output is correct |
6 |
Correct |
0 ms |
2228 KB |
Output is correct |
7 |
Correct |
0 ms |
2228 KB |
Output is correct |
8 |
Correct |
0 ms |
2228 KB |
Output is correct |
9 |
Correct |
0 ms |
2228 KB |
Output is correct |
10 |
Correct |
0 ms |
2228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
2228 KB |
Output is correct |
2 |
Correct |
0 ms |
2228 KB |
Output is correct |
3 |
Correct |
0 ms |
2228 KB |
Output is correct |
4 |
Correct |
0 ms |
2228 KB |
Output is correct |
5 |
Correct |
4 ms |
2228 KB |
Output is correct |
6 |
Correct |
8 ms |
2228 KB |
Output is correct |
7 |
Correct |
20 ms |
2228 KB |
Output is correct |
8 |
Correct |
28 ms |
2228 KB |
Output is correct |
9 |
Correct |
8 ms |
2228 KB |
Output is correct |
10 |
Correct |
12 ms |
2228 KB |
Output is correct |
11 |
Correct |
68 ms |
2228 KB |
Output is correct |
12 |
Correct |
40 ms |
2228 KB |
Output is correct |
13 |
Correct |
44 ms |
2228 KB |
Output is correct |
14 |
Correct |
56 ms |
2228 KB |
Output is correct |
15 |
Correct |
44 ms |
2228 KB |
Output is correct |
16 |
Correct |
92 ms |
2228 KB |
Output is correct |
17 |
Correct |
92 ms |
2228 KB |
Output is correct |
18 |
Correct |
92 ms |
2228 KB |
Output is correct |
19 |
Correct |
92 ms |
2228 KB |
Output is correct |
20 |
Correct |
92 ms |
2228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
2228 KB |
Output is correct |
2 |
Correct |
0 ms |
2228 KB |
Output is correct |
3 |
Correct |
0 ms |
2228 KB |
Output is correct |
4 |
Correct |
0 ms |
2228 KB |
Output is correct |
5 |
Correct |
4 ms |
2228 KB |
Output is correct |
6 |
Correct |
16 ms |
2228 KB |
Output is correct |
7 |
Correct |
20 ms |
2228 KB |
Output is correct |
8 |
Correct |
28 ms |
2228 KB |
Output is correct |
9 |
Correct |
8 ms |
2228 KB |
Output is correct |
10 |
Correct |
16 ms |
2228 KB |
Output is correct |
11 |
Correct |
64 ms |
2228 KB |
Output is correct |
12 |
Correct |
40 ms |
2228 KB |
Output is correct |
13 |
Correct |
44 ms |
2228 KB |
Output is correct |
14 |
Correct |
56 ms |
2228 KB |
Output is correct |
15 |
Correct |
44 ms |
2228 KB |
Output is correct |
16 |
Correct |
92 ms |
2228 KB |
Output is correct |
17 |
Correct |
92 ms |
2228 KB |
Output is correct |
18 |
Correct |
88 ms |
2228 KB |
Output is correct |
19 |
Correct |
92 ms |
2228 KB |
Output is correct |
20 |
Correct |
92 ms |
2228 KB |
Output is correct |