Submission #999921
Source Code Expand
#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007; const int INF = 1<<29; const double EPS = 1e-8; typedef vector<int> vec; typedef pair<int,int> P; typedef long long ll; ll N, M; ll memo[301][301][301]; ll dfs(int pos, int got, int next){ if(pos == M){ if(got == N) return 1; else return 0; } if(memo[pos][got][next] != -1) return memo[pos][got][next]; if(got == N) { return (N * dfs(pos+1, N, 0)) % MOD; } ll ret = 0; // go to nodes that has a path to node 1. // number of such nodes is `got` ret = (ret + got * dfs(pos+1, got+next, 0)) % MOD; // go to visited nodes that doesn't have a path to node 1. // number of such nodes is `next` ret = (ret + next * dfs(pos+1, got, next)) % MOD; // go to non visited nodes if it exists. // number of such nodes is `N - (got + next)` if (N - (got + next) > 0){ ret = (ret + (N - (got + next)) * dfs(pos+1, got, next+1)) % MOD; } memo[pos][got][next] = ret; return ret; } int main(){ cin >> N >> M; memset(memo, -1, sizeof(memo)); cout << dfs(0, 1, 0) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Road of the King |
User | zaburo |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 1233 Byte |
Status | AC |
Exec Time | 354 ms |
Memory | 213376 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 | 203 ms | 213248 KB |
01-02.txt | AC | 203 ms | 213248 KB |
01-03.txt | AC | 204 ms | 213376 KB |
01-04.txt | AC | 203 ms | 213248 KB |
01-05.txt | AC | 207 ms | 213376 KB |
01-06.txt | AC | 255 ms | 213376 KB |
01-07.txt | AC | 353 ms | 213376 KB |
01-08.txt | AC | 354 ms | 213376 KB |
01-09.txt | AC | 353 ms | 213376 KB |
01-10.txt | AC | 352 ms | 213376 KB |
sample-01.txt | AC | 202 ms | 213248 KB |
sample-02.txt | AC | 302 ms | 213376 KB |
sample-03.txt | AC | 221 ms | 213248 KB |