Submission #995276
Source Code Expand
#include <iostream> #include <fstream> #include <sstream> #include <vector> #include <set> #include <bitset> #include <map> #include <deque> #include <string> #include <algorithm> #include <numeric> #include <cstdio> #include <cassert> #include <cstdlib> #include <cstring> #include <ctime> #include <cmath> #define pb push_back #define pbk pop_back #define mp make_pair #define fs first #define sc second #define all(x) (x).begin(), (x).end() #define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i) #define len(a) ((int) (a).size()) #ifdef CUTEBMAING #define eprintf(...) fprintf(stderr, __VA_ARGS__) #else #define eprintf(...) 42 #endif using namespace std; typedef long long int64; typedef long double ld; typedef unsigned long long lint; const int inf = (1 << 30) - 1; const int64 linf = (1ll << 62) - 1; const int N = 400; const int M = 1e9 + 7; inline int power(int a, int b) { int res = 1; for (; b; b >>= 1) { if (b & 1) { res = (1ll * res * a) % M; } a = (1ll * a * a) % M; } return res; } int n, m; int wdp[N][N]; int dp[N][N]; int pw[N][N]; int fact[N], ifact[N]; inline int cnk(int n, int k) { return (((1ll * fact[n] * ifact[k]) % M) * ifact[n - k]) % M; } int main() { #ifdef XCODE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif cin >> n >> m; fact[0] = 1; ifact[0] = 1; for (int i = 1; i <= m; i++) { fact[i] = (1ll * fact[i - 1] * i) % M; ifact[i] = power(fact[i], M - 2); } for (int i = 0; i <= m; i++) { for (int j = 0; j <= m; j++) { pw[j][i] = i == 0 ? 1 : (1ll * pw[j][i - 1] * j) % M; } } for (int i = 0; i <= m; i++) { for (int j = 0; j <= i; j++) { wdp[i][j] = pw[j][i]; for (int z = 1; z < j; z++) { wdp[i][j] = (wdp[i][j] - 1ll * cnk(j, z) * wdp[i][j - z]) % M; if (wdp[i][j] < 0) { wdp[i][j] += M; } } } } dp[0][1] = 1; for (int i = 0; i < m; i++) { for (int j = 1; j <= n; j++) { if (!dp[i][j]) { continue; } for (int l = 0; j + l <= n; l++) { int cur2 = cnk(n - j, l); for (int z = 0; z <= m - i - 1; z++) { int cur = (((1ll * j * wdp[z][l]) % M) * cur2) % M; dp[i + z + 1][j + l] = (dp[i + z + 1][j + l] + 1ll * cur * dp[i][j]) % M; } } } } cout << dp[m][n] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Road of the King |
User | darinflar |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2750 Byte |
Status | TLE |
Exec Time | 3154 ms |
Memory | 1792 KB |
Judge Result
Set Name | sample | all | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 2 ms | 256 KB |
01-02.txt | AC | 3 ms | 256 KB |
01-03.txt | AC | 37 ms | 1664 KB |
01-04.txt | AC | 3 ms | 256 KB |
01-05.txt | AC | 53 ms | 1664 KB |
01-06.txt | AC | 1037 ms | 1664 KB |
01-07.txt | TLE | 3154 ms | 1664 KB |
01-08.txt | TLE | 3154 ms | 1664 KB |
01-09.txt | TLE | 3154 ms | 1792 KB |
01-10.txt | TLE | 3154 ms | 1664 KB |
sample-01.txt | AC | 3 ms | 256 KB |
sample-02.txt | AC | 2493 ms | 1664 KB |
sample-03.txt | AC | 8 ms | 896 KB |