#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
struct mint {
int v;
mint(long long x) {
if (x >= mod) x %= mod;
v = x;
}
mint() {v = 0;}
mint& operator+=(mint b) {
if ((v += b.v) >= mod) {
v -= mod;
}
return *this;
}
mint& operator-=(mint b) {
if ((v -= b.v) < 0) {
v += mod;
}
return *this;
}
mint& operator*=(mint b) {
v = 1ll * v * b.v % mod;
return *this;
}
mint power(mint a, int b) {
mint ans = 1;
while (b) {
if (b & 1) {
ans *= a;
}
a *= a, b >>= 1;
}
return ans;
}
mint& operator/=(mint b) {
v = 1ll * v * power(b, mod - 2).v % mod;
return *this;
}
friend mint operator+(mint a, mint b) {
return a += b;
}
friend mint operator-(mint a, mint b) {
return a -= b;
}
friend mint operator*(mint a, mint b) {
return a *= b;
}
friend mint operator/(mint a, mint b) {
return a /= b;
}
friend istream& operator>>(istream &is, mint a) {
return is >> a.v;
}
friend ostream& operator<<(ostream &os, mint a) {
return os << a.v;
}
};
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> st[n][2];
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
a--, b--;
if (a < b) {
//s[i - 1] > s[i]
st[a + 1][0].push_back(b + 1);
} else {
//s[i - 1] < s[i]
st[b + 1][1].push_back(a + 1);
}
}
mint dp[n + 1][26];
for (int j = 0; j < 26; j++) dp[n][j] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < 26; j++) {
dp[i][j] = 1;
int cnt[n + 1][2]{};
int cur[2]{};
for (int k = i + (i == 0); k < n; k++) {
for (int x = 0; x < 2; x++) {
cur[x] += cnt[k][x];
for (auto en : st[k][x]) {
cur[x]++;
cnt[en][x]--;
}
}
if (!cur[1]) {
for (int l = 0; l < j; l++) {
dp[i][j] += dp[k + 1][l];
}
}
if (!cur[0]) {
for (int l = j + 1; l < 26; l++) {
dp[i][j] += dp[k + 1][l];
}
}
}
}
}
mint ans = 0;
for (int j = 0; j < 26; j++) {
ans += dp[0][j];
}
cout << ans << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
23 ms |
488 KB |
Output is correct |
16 |
Correct |
7 ms |
344 KB |
Output is correct |
17 |
Correct |
5 ms |
348 KB |
Output is correct |
18 |
Correct |
3 ms |
348 KB |
Output is correct |
19 |
Correct |
4 ms |
348 KB |
Output is correct |
20 |
Correct |
4 ms |
348 KB |
Output is correct |
21 |
Correct |
5 ms |
856 KB |
Output is correct |
22 |
Correct |
17 ms |
604 KB |
Output is correct |
23 |
Correct |
17 ms |
348 KB |
Output is correct |
24 |
Correct |
5 ms |
348 KB |
Output is correct |
25 |
Correct |
3 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
352 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Execution timed out |
4046 ms |
100524 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
23 ms |
488 KB |
Output is correct |
16 |
Correct |
7 ms |
344 KB |
Output is correct |
17 |
Correct |
5 ms |
348 KB |
Output is correct |
18 |
Correct |
3 ms |
348 KB |
Output is correct |
19 |
Correct |
4 ms |
348 KB |
Output is correct |
20 |
Correct |
4 ms |
348 KB |
Output is correct |
21 |
Correct |
5 ms |
856 KB |
Output is correct |
22 |
Correct |
17 ms |
604 KB |
Output is correct |
23 |
Correct |
17 ms |
348 KB |
Output is correct |
24 |
Correct |
5 ms |
348 KB |
Output is correct |
25 |
Correct |
3 ms |
348 KB |
Output is correct |
26 |
Execution timed out |
4032 ms |
4180 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
23 ms |
488 KB |
Output is correct |
16 |
Correct |
7 ms |
344 KB |
Output is correct |
17 |
Correct |
5 ms |
348 KB |
Output is correct |
18 |
Correct |
3 ms |
348 KB |
Output is correct |
19 |
Correct |
4 ms |
348 KB |
Output is correct |
20 |
Correct |
4 ms |
348 KB |
Output is correct |
21 |
Correct |
5 ms |
856 KB |
Output is correct |
22 |
Correct |
17 ms |
604 KB |
Output is correct |
23 |
Correct |
17 ms |
348 KB |
Output is correct |
24 |
Correct |
5 ms |
348 KB |
Output is correct |
25 |
Correct |
3 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
352 KB |
Output is correct |
28 |
Correct |
1 ms |
600 KB |
Output is correct |
29 |
Correct |
1 ms |
344 KB |
Output is correct |
30 |
Execution timed out |
4046 ms |
100524 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |