Submission #994837
Source Code Expand
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>
//#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define veccat(v1, v2) std::copy((v2).begin(),(v2).end(),std::back_inserter(v1)/*v1の後ろにv2を入れる*/)
#define intmax (std::numeric_limits<int64_t>::max() / 4)
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);
class modint {
//MODが素数であることを前提として実装してあるが、その判定はしていない。
//あまりが出るような除算をしてはいけない。
private:
static const int MOD = 1000000007;
public:
modint() {
//assert(is_prime(MOD));
this->number = 0;
}
modint(const int src) {
//assert(is_prime(MOD));
this->number = opposit(src);
}
modint(const modint &src) {
this->number = src.number;
}
modint& operator += (const modint& obj) {
this->number = san2(this->number + obj.number);
return *this;
}
modint& operator -= (const modint& obj) {
this->number = san2(this->number - obj.number + MOD);
return *this;
}
modint& operator *= (const modint& obj) {
this->number = (this->number * obj.number) % MOD;
return *this;
}
modint& operator /= (const modint& obj) {
this->number = (this->number * inverse(obj.number)) % MOD;
return *this;
}
modint& operator += (const int n) {
this->number = san2(this->number + opposit(n));
return *this;
}
modint& operator -= (const int n) {
this->number = san2(this->number - opposit(n) + MOD);
return *this;
}
modint& operator *= (const int n) {
this->number = (this->number * opposit(n)) % MOD;
return *this;
}
modint& operator /= (const int n) {
this->number = (this->number * inverse(n)) % MOD;
return *this;
}
modint operator + (const modint obj) { modint re(*this); return re += obj; }
modint operator - (const modint obj) { modint re(*this); return re -= obj; }
modint operator * (const modint obj) { modint re(*this); return re *= obj; }
modint operator / (const modint obj) { modint re(*this); return re /= obj; }
modint operator + (const int n) { modint re(*this); return re += n; }
modint operator - (const int n) { modint re(*this); return re -= n; }
modint operator * (const int n) { modint re(*this); return re *= n; }
modint operator / (const int n) { modint re(*this); return re /= n; }
modint operator = (const int n) {
this->number = opposit(n);
return *this;
}
int get() {
return number;
}
private:
int number;
int opposit(int n) {
if (n < 0)n = MOD - ((-n) % MOD);
return n % MOD;
}
int inverse(int n) {
n = opposit(n);
int result = 1;
for (int i = MOD - 2; i; i /= 2) {
if (i % 2)result = (result * n) % MOD;
n = (n * n) % MOD;
}
return result;
}
inline int san2(const int n) {
return MOD <= n ? n - MOD : n;
}
bool is_prime(int n) {
if (n <= 1)return false;
if (n == 2)return true;
if (n % 2 == 0) return false;
const int upperbound = int(sqrt(n));
for (int i = 3; i <= upperbound; i += 2) {
if (n % i == 0) return false;
}
return true;
}
};
int N, M;
int memo[301][301][301];
modint facto[1000];
modint solve(int amari, int maxnum, int sentaku) {
if (amari < 0)return 0;
if (amari == 0)return 1;
if (sentaku * maxnum < amari)return 0;
if (memo[amari][maxnum][sentaku] != -1)return memo[amari][maxnum][sentaku];
modint ans = 1;
for (int i = maxnum; 1 <= i; i--) {
ans += solve(amari - i, i, sentaku - 1) * (facto[M-amari+i] / facto[i+1]);
}
memo[amari][maxnum][sentaku] = ans.get();
return ans;
}
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N >> M;
facto[0] = 1;
REP(i, 1, 1000)facto[i] = facto[i - 1] * i;
if (M < N) {
cout << 0 << endl;
return 0;
}
rep(i, 301)rep(j, 301)rep(k, 301)memo[i][j][k] = -1;
modint ans = facto[N - 1];
int amari = M - N;
ans *= solve(amari, amari, N);
cout << ans.get() << endl;
}
Submission Info
Submission Time |
|
Task |
F - Road of the King |
User |
eukaryo |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4782 Byte |
Status |
WA |
Exec Time |
499 ms |
Memory |
213376 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 |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
2 ms |
256 KB |
01-02.txt |
AC |
182 ms |
213376 KB |
01-03.txt |
WA |
187 ms |
213376 KB |
01-04.txt |
AC |
2 ms |
256 KB |
01-05.txt |
WA |
499 ms |
213376 KB |
01-06.txt |
WA |
350 ms |
213376 KB |
01-07.txt |
WA |
182 ms |
213376 KB |
01-08.txt |
WA |
183 ms |
213376 KB |
01-09.txt |
WA |
183 ms |
213376 KB |
01-10.txt |
AC |
183 ms |
213376 KB |
sample-01.txt |
AC |
182 ms |
213376 KB |
sample-02.txt |
WA |
246 ms |
213376 KB |
sample-03.txt |
AC |
2 ms |
256 KB |