Submission #1454245


Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
inline void add(int &x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
}

int N, M;
int dp[301][301][301];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M;

  dp[0][1][1] = 1;
  rep(i, M) {
    rep(j, N+1) {
      rep(k, j+1) {
        if (j < N) {
          add(dp[i+1][j+1][k], (1LL*(N-j)*dp[i][j][k]) % MOD);
        }
        add(dp[i+1][j][j], (1LL*  k  *dp[i][j][k]) % MOD);
        add(dp[i+1][j][k], (1LL*(j-k)*dp[i][j][k]) % MOD);
      }
    }
  }
  cout << dp[M][N][N] << "\n";
  return 0;
}

Submission Info

Submission Time
Task F - Road of the King
User funcsr
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 1058 Byte
Status AC
Exec Time 141 ms
Memory 106496 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 3
AC × 16
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 AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 22 ms 104704 KB
01-04.txt AC 2 ms 640 KB
01-05.txt AC 22 ms 104832 KB
01-06.txt AC 38 ms 105216 KB
01-07.txt AC 135 ms 106368 KB
01-08.txt AC 140 ms 106496 KB
01-09.txt AC 141 ms 106496 KB
01-10.txt AC 141 ms 106496 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 62 ms 105600 KB
sample-03.txt AC 57 ms 55168 KB