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
AC × 3
AC × 13
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