#include<stdio.h>
#include<algorithm>
using namespace std;
int n, m, R;
int w[251][2];
long long R1, R2, Mod = 1000000007, D[2][251][251];
void Do(int x){
int i, j, k;
for (i = 0; i <= n; i++){
for (j = 0; j < R; j++){
D[0][i][j] = D[1][i][j] = 0;
}
}
D[0][0][0] = 1;
for (i = 1; i <= n; i++){
for (j = 0; j < R; j++){
if (!D[0][i - 1][j] && !D[1][i - 1][j])continue;
D[0][i - 1][j] %= Mod;
D[1][i - 1][j] %= Mod;
if (w[i][0] <= x && x <= w[i][1] && j != R-1){
D[1][i][j + 1] = D[1][i][j + 1] + D[0][i - 1][j] + D[1][i - 1][j];
}
for (k = 0; k < 2; k++){
if (w[i][0] < x){
D[k][i][j] = D[k][i][j] + D[k][i - 1][j] * (min(x - 1, w[i][1]) - w[i][0] + 1);
}
if (w[i][1] > x && j != R - 1){
D[k][i][j + 1] = D[k][i][j + 1] + D[k][i - 1][j] * (w[i][1] - max(w[i][0], x + 1) + 1);
}
}
}
}
R2 = (R2 + D[1][n][R - 1]) % Mod;
for (i = 0; i <= n; i++){
for (j = 0; j < R; j++){
D[0][i][j] = D[1][i][j] = 0;
}
}
}
int main()
{
int i;
scanf("%d%d", &n, &m);
R1 = 1;
for (i = 1; i <= n; i++){
scanf("%d%d", &w[i][0], &w[i][1]);
R1 = R1*(w[i][1] - w[i][0] + 1) % Mod;
}
scanf("%d", &R);
if (R == 1){
printf("0\n");
return 0;
}
for (i = 0; i <= m; i++){
Do(i);
}
printf("%lld\n", (R1 - R2 + Mod) % Mod);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2072 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2072 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 11 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 12 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 13 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 14 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 16 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 17 |
Correct |
4 ms |
2072 KB |
Output is correct |
| 18 |
Correct |
4 ms |
2072 KB |
Output is correct |
| 19 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 20 |
Correct |
8 ms |
2072 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 4 |
Correct |
8 ms |
2072 KB |
Output is correct |
| 5 |
Correct |
20 ms |
2072 KB |
Output is correct |
| 6 |
Correct |
28 ms |
2072 KB |
Output is correct |
| 7 |
Correct |
24 ms |
2072 KB |
Output is correct |
| 8 |
Correct |
80 ms |
2072 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 10 |
Correct |
48 ms |
2072 KB |
Output is correct |
| 11 |
Correct |
40 ms |
2072 KB |
Output is correct |
| 12 |
Correct |
12 ms |
2072 KB |
Output is correct |
| 13 |
Correct |
112 ms |
2072 KB |
Output is correct |
| 14 |
Correct |
32 ms |
2072 KB |
Output is correct |
| 15 |
Correct |
124 ms |
2072 KB |
Output is correct |
| 16 |
Correct |
192 ms |
2072 KB |
Output is correct |
| 17 |
Correct |
196 ms |
2072 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2072 KB |
Output is correct |
| 19 |
Correct |
352 ms |
2072 KB |
Output is correct |
| 20 |
Correct |
696 ms |
2072 KB |
Output is correct |
