#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX = 420, MOD = 1000000007;
int n, m, a[MAX], b[MAX], target;
void input(){
scanf("%d%d", &n, &m);
int i;
for(i = 1; i<=n; i++)
scanf("%d%d", &a[i], &b[i]);
scanf("%d", &target);
}
void add(int &t, ll val){
val += t;
t = val%MOD;
}
int dp[MAX][2][2];
void solve(){
int res = 1, i, j, k;
for(i = 1; i<=n; i++)
res = (ll)res*(b[i]-a[i]+1)%MOD;
for(i = 0; i<=m; i++){
for(k = 0; k<=target-1; k++){
dp[k][0][0] = 0;
dp[k][0][1] = 0;
dp[k][1][0] = 0;
dp[k][1][1] = 0;
}
dp[0][0][0] = 1;
for(j = 1; j<=n; j++){
bool c = j&1;
for(k = 0; k<=target-1; k++){
ll up = max(0, min(b[j]-i, b[j]-a[j]+1));
ll mid = a[j] <= i && i <= b[j];
ll down = max(0, min(i-a[j], b[j]-a[j]+1));
//m+1 ~ b[j]
add(dp[k+1][0][c], dp[k][0][!c]*up);
add(dp[k+1][1][c], dp[k][1][!c]*up);
//m
add(dp[k][1][c], dp[k][0][!c]*mid);
add(dp[k][1][c], dp[k][1][!c]*mid);
//a[j] ~ m-1
add(dp[k][0][c], dp[k][0][!c]*down);
add(dp[k][1][c], dp[k][1][!c]*down);
}
for(k = 0; k<=target-1; k++){
dp[k][0][!c] = 0;
dp[k][1][!c] = 0;
}
}
add(res, MOD-dp[target-1][1][n&1]);
}
printf("%d\n", res);
}
int main(){
input();
solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1096 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1096 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1096 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 16 |
Correct |
4 ms |
1096 KB |
Output is correct |
| 17 |
Correct |
4 ms |
1096 KB |
Output is correct |
| 18 |
Correct |
4 ms |
1096 KB |
Output is correct |
| 19 |
Correct |
4 ms |
1096 KB |
Output is correct |
| 20 |
Correct |
4 ms |
1096 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1096 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1096 KB |
Output is correct |
| 5 |
Correct |
24 ms |
1096 KB |
Output is correct |
| 6 |
Correct |
28 ms |
1096 KB |
Output is correct |
| 7 |
Correct |
24 ms |
1096 KB |
Output is correct |
| 8 |
Correct |
96 ms |
1096 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1096 KB |
Output is correct |
| 10 |
Correct |
56 ms |
1096 KB |
Output is correct |
| 11 |
Correct |
44 ms |
1096 KB |
Output is correct |
| 12 |
Correct |
16 ms |
1096 KB |
Output is correct |
| 13 |
Correct |
124 ms |
1096 KB |
Output is correct |
| 14 |
Correct |
32 ms |
1096 KB |
Output is correct |
| 15 |
Correct |
140 ms |
1096 KB |
Output is correct |
| 16 |
Correct |
200 ms |
1096 KB |
Output is correct |
| 17 |
Correct |
212 ms |
1096 KB |
Output is correct |
| 18 |
Correct |
4 ms |
1096 KB |
Output is correct |
| 19 |
Correct |
448 ms |
1096 KB |
Output is correct |
| 20 |
Correct |
408 ms |
1096 KB |
Output is correct |
