Submission #11352484
Source Code Expand
#include <bits/stdc++.h> using namespace std; const long long MOD=1e9+7; template<uint_fast64_t Modulus> class modint{ using u64=uint_fast64_t; public: u64 a; constexpr modint(const u64 x=0) noexcept:a(((x%Modulus)+Modulus)%Modulus){} constexpr u64 &value() noexcept{return a;} constexpr const u64 &value() const noexcept{return a;} constexpr modint &operator+=(const modint &rhs) noexcept{ a+=rhs.a; if (a>=Modulus) a-=Modulus; return *this; } constexpr modint operator+(const modint &rhs) const noexcept{ return modint(*this)+=rhs; } constexpr modint &operator++() noexcept{ return ++a,*this; } constexpr modint operator++(int) noexcept{ modint t=*this; return ++a,t; } constexpr modint &operator-=(const modint &rhs) noexcept{ if (a<rhs.a) a+=Modulus; a-=rhs.a; return *this; } constexpr modint operator-(const modint &rhs) const noexcept{ return modint(*this)-=rhs; } constexpr modint &operator--() noexcept{ return --a,*this; } constexpr modint operator--(int) noexcept{ modint t=*this; return --a,t; } constexpr modint &operator*=(const modint &rhs) noexcept{ a=a*rhs.a%Modulus; return *this; } constexpr modint operator*(const modint &rhs) const noexcept{ return modint(*this)*=rhs; } constexpr modint &operator/=(modint rhs) noexcept{ u64 exp=Modulus-2; while(exp){ if (exp&1) *this*=rhs; rhs*=rhs; exp>>=1; } return *this; } constexpr modint operator/(const modint &rhs) const noexcept{ return modint(*this)/=rhs; } constexpr modint operator-() const noexcept{ return modint(Modulus-a); } constexpr bool operator==(const modint &rhs) const noexcept{ return a==rhs.a; } constexpr bool operator!=(const modint &rhs) const noexcept{ return a!=rhs.a; } constexpr bool operator!() const noexcept{return !a;} friend constexpr modint pow(modint rhs,long long exp) noexcept{ modint res{1}; while(exp){ if (exp&1) res*=rhs; rhs*=rhs; exp>>=1; } return res; } template<class T> friend constexpr modint operator+(T x,modint y) noexcept{ return modint(x)+y; } template<class T> friend constexpr modint operator-(T x,modint y) noexcept{ return modint(x)-y; } template<class T> friend constexpr modint operator*(T x,modint y) noexcept{ return modint(x)*y; } template<class T> friend constexpr modint operator/(T x,modint y) noexcept{ return modint(x)/y; } friend ostream &operator<<(ostream &s,const modint &rhs) noexcept { return s << rhs.a; } friend istream &operator>>(istream &s,modint &rhs) noexcept { u64 a; rhs=modint{(s >> a,a)}; return s; } }; using mint=modint<MOD>; int N,M; const int MAX_NM=310; mint dp[MAX_NM][MAX_NM][MAX_NM][2]; int main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M; dp[0][0][0][0]=1; for (int i=0;i<M;++i){ for (int j=0;j<N;++j){ for (int k=0;k<N;++k){ dp[i+1][j][k][0]+=dp[i][j][k][0]*(k+1); dp[i+1][j][k][1]+=dp[i][j][k][0]*(j-k); if (j+1<N) dp[i+1][j+1][k][1]+=dp[i][j][k][0]*(N-j-1); dp[i+1][j][j][0]+=dp[i][j][k][1]*(k+1); dp[i+1][j][k][1]+=dp[i][j][k][1]*(j-k); if (j+1<N) dp[i+1][j+1][k][1]+=dp[i][j][k][1]*(N-j-1); } } } cout << dp[M][N-1][N-1][0] << '\n'; }
Submission Info
Submission Time | |
---|---|
Task | F - Road of the King |
User | rniya |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3810 Byte |
Status | MLE |
Exec Time | 503 ms |
Memory | 451328 KB |
Judge Result
Set Name | sample | all | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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, 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 | 2 ms | 2304 KB |
01-03.txt | MLE | 88 ms | 448768 KB |
01-04.txt | AC | 3 ms | 2816 KB |
01-05.txt | MLE | 88 ms | 448768 KB |
01-06.txt | MLE | 130 ms | 451200 KB |
01-07.txt | MLE | 476 ms | 449280 KB |
01-08.txt | MLE | 498 ms | 451328 KB |
01-09.txt | MLE | 500 ms | 451328 KB |
01-10.txt | MLE | 503 ms | 451328 KB |
sample-01.txt | AC | 2 ms | 4352 KB |
sample-02.txt | MLE | 203 ms | 451328 KB |
sample-03.txt | AC | 237 ms | 226048 KB |