Submission #993340
Source Code Expand
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using D = double; using uint = unsigned int; #ifdef WIN32 #define LLD "%I64d" #else #define LLD "%lld" #endif #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second const int MOD = 1000000007; const int maxn = 305; int cnk[maxn][maxn]; int ans[maxn][maxn]; int ans2[maxn][maxn][maxn]; int kk[maxn][maxn]; int pw[maxn][maxn]; int n, m; int f[maxn]; void add(int &x, ll y) { x = (x + y) % MOD; } int main() { scanf("%d%d", &n, &m); cnk[0][0] = 1; for (int i = 1; i <= n; i++) { cnk[i][0] = 1; for (int j = 1; j <= i; j++) cnk[i][j] = (cnk[i - 1][j - 1] + cnk[i - 1][j]) % MOD; } f[0] = 1; for (int i = 1; i <= n; i++) f[i] = ((ll)f[i - 1] * i) % MOD; for (int i = 1; i <= n; i++) { pw[i][0] = 1; for (int j = 1; j <= m; j++) pw[i][j] = ((ll)pw[i][j - 1] * i) % MOD; } kk[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = i; j <= m; j++) { for (int t = i; t >= i; t--) add(kk[i][j], (((ll)kk[i - 1][t - 1] * pw[i][j - t]) % MOD) * i); } } // cout << f[n - 1] << endl; // ans[0][1] = 1; // for (int i = 0; i < m; i++) // { // for (int j = 1; j <= n; j++) if (ans[i][j] != 0) // { // // cout << i << ' ' << j << ' ' << ans[i][j] << endl; // for (int k = 0; k <= n - j && i + k + 1 <= m; k++) // { // for (int t = 0; i + k + t + 1 <= m; t++) // { // add(ans[i + k + t + 1][j + k], (((ll)ans[i][j] * kk[k][k + t]) % MOD) * j); // } // } // } // } // cout << ans[m][n] << endl; ans2[0][1][0] = 1; for (int i = 0; i < m; i++) { for (int j = 1; j <= n; j++) { for (int k = 0; k + j <= n; k++) if (ans2[i][j][k] != 0) { add(ans2[i + 1][j + k][0], ((ll)ans2[i][j][k] * j)); add(ans2[i + 1][j][k], ((ll)ans2[i][j][k] * k)); add(ans2[i + 1][j][k + 1], ((ll)ans2[i][j][k] * (n - j - k))); } } } int answer = 0; for (int i = 0; i < n; i++) add(answer, ans2[m][n][i]); cout << answer << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Road of the King |
User | KAN |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2486 Byte |
Status | AC |
Exec Time | 165 ms |
Memory | 55936 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:40:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &n, &m); ^
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 | 256 KB |
01-02.txt | AC | 3 ms | 256 KB |
01-03.txt | AC | 6 ms | 1792 KB |
01-04.txt | AC | 4 ms | 1024 KB |
01-05.txt | AC | 11 ms | 4608 KB |
01-06.txt | AC | 63 ms | 28544 KB |
01-07.txt | AC | 162 ms | 55552 KB |
01-08.txt | AC | 165 ms | 55936 KB |
01-09.txt | AC | 164 ms | 55936 KB |
01-10.txt | AC | 164 ms | 55936 KB |
sample-01.txt | AC | 3 ms | 256 KB |
sample-02.txt | AC | 100 ms | 41984 KB |
sample-03.txt | AC | 56 ms | 15104 KB |