Submission #10059085
Source Code Expand
#include <iostream> #include <map> #include <set> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <fstream> #include <bitset> #include <queue> #include <stack> #include <deque> #include <complex> #include <iomanip> #include <stdio.h> #include <string.h> #include <random> #include <functional> using std::cin; using std::cout; using std::cerr; using std::endl; using std::map; using std::set; using std::bitset; using std::vector; using std::string; using std::multimap; using std::multiset; using std::deque; using std::queue; using std::stack; using std::pair; using std::iterator; using std::sort; using std::stable_sort; using std::reverse; using std::max_element; using std::min_element; using std::unique; using std::ios_base; using std::swap; using std::fill; using std::setprecision; using std::fixed; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<long long> vl; typedef string S; ll min(ll a, ll b) {return a < b ? a : b;} ll min(int a, ll b) {return a < b ? a : b;} ll min(ll a, int b) {return a < b ? a : b;} ll min(int a, int b) {return a < b ? a : b;} ll max(ll a, ll b) {return a > b ? a : b;} ll max(int a, ll b) {return a > b ? a : b;} ll max(ll a, int b) {return a > b ? a : b;} ll max(int a, int b) {return a > b ? a : b;} namespace MySpace{ }; #define F(i, n) for (int (i) = 0; (i) != (n); (i)++) #define fi first #define se second #define re return #define all(x) (x).begin(), (x).end() const int MOD = 1e9 + 7; const int K = 100; long long inq(long long a, long long b) { if (b == 0) return 1; long long l = inq(a, b / 2); if (b % 2) return l * l % MOD * a % MOD; return l * l % MOD; } int n0, m0; long long fact[5000], ufact[5000]; long long dp[K][K][K]; long long ways[K][K][K]; long long cnk(long long x, long long k) { return fact[x] * ufact[k] % MOD * ufact[x - k] % MOD; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n0 >> m0; fact[0] = 1, ufact[0] = 1; for (int i = 1; i <= K; i++) fact[i] = 1LL * fact[i - 1] * i % MOD, ufact[i] = inq(fact[i], MOD - 2); for (int all = 0; all <= n0 + 1; all++) { ways[0][all][0] = 1; for (int i = 0; i < K; i++) { for (int j = 0; j <= all; j++) { ways[i + 1][all][j] = (ways[i + 1][all][j] + ways[i][all][j] * j) % MOD; ways[i + 1][all][j + 1] = (ways[i + 1][all][j + 1] + ways[i][all][j] * (all - j)) % MOD; } } } for (int all = 0; all <= n0 + 1; all++) { for (int x = 0; x <= K; x++) { for (int y = 0; y <= all; y++) { ways[x][all][y] = ways[x][all][y] * inq(cnk(all, y), MOD - 2) % MOD; ways[x][all][y] = ways[x][all][y] * ufact[y] % MOD; } } for (int x = 0; x <= K; x++) { for (int y = all - 1; y >= 0; y--) ways[x][all][y] = (ways[x][all][y] + ways[x][all][y + 1] * all) % MOD; } } dp[0][1][0] = 1; for (int pos = 1; pos <= m0; pos++) { for (int last = 1; last <= n0; last++) { for (int pr = 0; pr < pos; pr++) { for (int wri = 0; wri < last; wri++) { for (int blo = 0; blo <= wri; blo++) { dp[pos][last][wri] = (dp[pos][last][wri] + 1LL * dp[pr][wri][blo] * ways[pos - pr - 1][last - blo][last - wri] % MOD * (wri - blo)) % MOD; } } } } } /*cout << endl; for (int i = 0; i <= m0; i++) { for (int j = 0; j <= n0; j++) { long long s = 0; for (int k = 0; k <= j; k++) s = (s + dp[i][j][k]) % MOD; cout << s << " "; } cout << endl; }*/ long long ans = 0; for (int pos = 0; pos <= m0; pos++) { for (int written = n0; written <= n0; written++) for (int blocked = 0; blocked <= written; blocked++) { ans = (ans + dp[pos][written][blocked] * ways[m0 - pos][n0 - blocked][n0 - written]) % MOD; } } cout << ans * fact[n0 - 1] % MOD; }
Submission Info
Submission Time | |
---|---|
Task | F - Road of the King |
User | IgorI |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 4516 Byte |
Status | RE |
Exec Time | 3156 ms |
Memory | 15360 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, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | WA | 3 ms | 6528 KB |
01-02.txt | WA | 3 ms | 6528 KB |
01-03.txt | RE | 100 ms | 12800 KB |
01-04.txt | AC | 1290 ms | 8448 KB |
01-05.txt | RE | 107 ms | 13056 KB |
01-06.txt | TLE | 3156 ms | 15360 KB |
01-07.txt | TLE | 3155 ms | 10496 KB |
01-08.txt | TLE | 3155 ms | 10496 KB |
01-09.txt | TLE | 3155 ms | 10496 KB |
01-10.txt | TLE | 3155 ms | 10496 KB |
sample-01.txt | WA | 3 ms | 6656 KB |
sample-02.txt | TLE | 3155 ms | 12544 KB |
sample-03.txt | TLE | 3155 ms | 10496 KB |