Submission #993151
Source Code Expand
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
mt19937 mrand(random_device{} ());
int rnd(int x) {
return mrand() % x;
}
typedef long double ld;
typedef long long ll;
#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif
#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"
const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);
void precalc() {
}
const int mod = (int) 1e9 + 7;
void add(int &x, int y) {
if ((x += y) >= mod) {
x -= mod;
}
}
int mult(int x, int y) {
return (long long) x * y % mod;
}
int myPower(int x, int pw) {
int res = 1;
for (; pw; pw >>= 1) {
if (pw & 1) {
res = mult(res, x);
}
x = mult(x, x);
}
return res;
}
int n, m;
int read() {
if (scanf("%d%d", &n, &m) < 2) {
return 0;
}
return 1;
}
const int maxn = (int) 3e2 + 10;
int dp[2][maxn][maxn];
void solve() {
memset(dp, 0, sizeof(dp));
int rot = 0;
dp[rot][1][1] = 1;
for (int iter = 1; iter <= m; ++iter) {
memset(dp[!rot], 0, sizeof(dp[!rot]));
for (int j = 1; j <= n; ++j) {
for (int into = 1; into <= j; ++into) {
int cur = dp[rot][j][into];
if (!cur) {
continue;
}
if (j < n) {
add(dp[!rot][j + 1][into], mult(cur, n - j));
}
add(dp[!rot][j][into], mult(cur, j - into));
add(dp[!rot][j][j], mult(cur, into));
}
}
rot = !rot;
}
printf("%d\n", dp[rot][n][n]);
}
int main() {
precalc();
#ifdef LOCAL
freopen(TASK ".out", "w", stdout);
assert(freopen(TASK ".in", "r", stdin));
#endif
while (1) {
if (!read()) {
break;
}
solve();
#ifdef DEBUG
eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Road of the King |
User |
XraY |
Language |
C++14 (GCC 5.4.1) |
Score |
1000 |
Code Size |
2001 Byte |
Status |
AC |
Exec Time |
78 ms |
Memory |
1024 KB |
Judge Result
Set Name |
sample |
all |
Score / Max Score |
0 / 0 |
1000 / 1000 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt, sample-03.txt |
all |
sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
3 ms |
1024 KB |
01-02.txt |
AC |
3 ms |
1024 KB |
01-03.txt |
AC |
8 ms |
1024 KB |
01-04.txt |
AC |
3 ms |
1024 KB |
01-05.txt |
AC |
8 ms |
1024 KB |
01-06.txt |
AC |
22 ms |
1024 KB |
01-07.txt |
AC |
76 ms |
1024 KB |
01-08.txt |
AC |
78 ms |
1024 KB |
01-09.txt |
AC |
77 ms |
1024 KB |
01-10.txt |
AC |
78 ms |
1024 KB |
sample-01.txt |
AC |
3 ms |
1024 KB |
sample-02.txt |
AC |
40 ms |
1024 KB |
sample-03.txt |
AC |
18 ms |
1024 KB |