Submission #1001485
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second const ll mod=1e9+7; const int N=300; // i日目,訪れた頂点数j,町1と強連結成分をなす町の個数k ll dp[N+1][N+1][N+1]={0}; int main() { int n,m; cin >>n >>m; dp[0][1][1]=1; rep(i,m)for(int j=1; j<=N; ++j)for(int k=1; k<=j; ++k) { // 町1との強連結成分内の町に行く (dp[i+1][j][j]+=dp[i][j][k]*k)%=mod; // 町1との強連結成分外の訪問済みの町に行く (dp[i+1][j][k]+=dp[i][j][k]*(j-k))%=mod; // 未訪問の町に行く if(j<N) (dp[i+1][j+1][k]+=dp[i][j][k]*(n-j))%=mod; } cout << dp[m][n][n] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Road of the King |
User | imulan |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 969 Byte |
Status | AC |
Exec Time | 471 ms |
Memory | 212608 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 | 4 ms | 896 KB |
01-02.txt | AC | 6 ms | 1664 KB |
01-03.txt | AC | 471 ms | 212608 KB |
01-04.txt | AC | 4 ms | 896 KB |
01-05.txt | AC | 466 ms | 212608 KB |
01-06.txt | AC | 465 ms | 212608 KB |
01-07.txt | AC | 469 ms | 211840 KB |
01-08.txt | AC | 466 ms | 212608 KB |
01-09.txt | AC | 469 ms | 212608 KB |
01-10.txt | AC | 466 ms | 212608 KB |
sample-01.txt | AC | 8 ms | 2304 KB |
sample-02.txt | AC | 466 ms | 212608 KB |
sample-03.txt | AC | 238 ms | 106368 KB |