Submission #993357


Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
ll mod=1e9+7;
void add(ll &x,ll y){
	x+=y;
	x%=mod;
}
ll dp[2][300][300];
int main(){
	int N,M;
	cin>>N>>M;
	dp[0][0][0]=1;
	rep(i,M){
		rep(a,N) rep(x,N) dp[1-i%2][a][x]=0;
		rep(a,N) rep(x,N) if(dp[i%2][a][x]){
			ll& val=dp[i%2][a][x];
			if(a!=N-1) add(dp[1-i%2][a+1][x],val);
			add(dp[1-i%2][a][a],val*(x+1));
			add(dp[1-i%2][a][x],val*(a-x));
		}
	}
	ll ans=dp[M%2][N-1][N-1];
	rep1(i,N-1) ans=ans*i%mod;
	cout<<ans<<endl;
}

Submission Info

Submission Time
Task F - Road of the King
User sigma425
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 1093 Byte
Status AC
Exec Time 174 ms
Memory 1664 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 3 ms 256 KB
01-02.txt AC 2 ms 256 KB
01-03.txt AC 2 ms 256 KB
01-04.txt AC 3 ms 896 KB
01-05.txt AC 3 ms 256 KB
01-06.txt AC 36 ms 640 KB
01-07.txt AC 170 ms 1664 KB
01-08.txt AC 174 ms 1664 KB
01-09.txt AC 174 ms 1664 KB
01-10.txt AC 174 ms 1664 KB
sample-01.txt AC 2 ms 256 KB
sample-02.txt AC 81 ms 896 KB
sample-03.txt AC 37 ms 1664 KB