| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 199032 | popovicirobert | Fishing Game (RMI19_fishing) | C++14 | 828 ms | 32248 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
template <typename T, T MOD>
class ModInt;
template <typename T, T MOD>
ModInt<T, MOD> lgpow(ModInt<T, MOD> a, ll b) {
assert(b >= 0);
ModInt<T, MOD> ans(1);
while(b > 0) {
if(b & 1) ans *= a;
b >>= 1, a *= a;
}
return ans;
}
template <typename T, T MOD>
ModInt<T, MOD> inv(ModInt<T, MOD> a) {
return lgpow(a, MOD - 2);
}
template <typename T, T MOD>
class ModInt {
protected:
T val;
inline T mod(ll x) const {
if(llabs(x) >= MOD) {
x %= MOD;
}
return (x < 0 ? MOD : 0) + x;
}
public:
explicit ModInt(ll _val = 0) : val(mod(_val)) {}
ModInt(const ModInt &y) : val(y.val) {}
ModInt operator +(const ModInt &y) const {
return ModInt(mod(val + y.val));
}
ModInt operator +(const ll &y) const {
return *this + ModInt(y);
}
ModInt operator -(const ModInt &y) const {
return ModInt(mod(val - y.val));
}
ModInt operator -(const ll &y) const {
return *this - ModInt(y);
}
ModInt operator *(const ModInt &y) const {
return ModInt(mod(1LL * val * y.val));
}
ModInt operator *(const ll &y) const {
return *this * ModInt(y);
}
ModInt operator /(const ModInt &y) const {
return ModInt(mod(1LL * val * inv(y).val));
}
ModInt operator /(const ll &y) const {
return *this / ModInt(y);
}
ModInt& operator =(const ModInt &y) {
val = y.val;
return *this;
}
ModInt& operator =(const ll &y) {
val = mod(y);
return *this;
}
bool operator ==(const ModInt &y) const {
return val == y.val;
}
bool operator ==(const T &y) const {
return val == y;
}
bool operator !=(const ModInt &y) const {
return val != y.val;
}
bool operator !=(const T &y) const {
return val != y;
}
bool operator <(const ModInt &y) const {
return val < y.val;
}
bool operator <(const T &y) const {
return val < y;
}
bool operator <=(const ModInt &y) const {
return val <= y.val;
}
bool operator <=(const T &y) const {
return val <= y;
}
bool operator >(const ModInt &y) const {
return val > y.val;
}
bool operator >(const T &y) const {
return val > y;
}
bool operator >=(const ModInt &y) const {
return val >= y.val;
}
bool operator >=(const T &y) const {
return val >= y;
}
ModInt& operator +=(const ModInt &y) {
val = mod(val + y.val);
return *this;
}
ModInt& operator +=(const T &y) {
val = mod(val + y);
return *this;
}
ModInt& operator -=(const ModInt &y) {
val = mod(val - y.val);
return *this;
}
ModInt& operator -=(const T &y) {
val = mod(val - y);
return *this;
}
ModInt& operator *=(const ModInt &y) {
val = mod(1LL * val * y.val);
return *this;
}
ModInt& operator *=(const T &y) {
val = mod(1LL * val * y);
return *this;
}
ModInt& operator /=(const ModInt &y) {
val = mod(1LL * val * inv(y.val));
return *this;
}
ModInt& operator /=(const T &y) {
val = mod(1LL * val * inv(y));
return *this;
}
ModInt& operator ++() {
val = mod(val + 1);
return *this;
}
ModInt operator ++(int) {
ModInt ans(val);
val = mod(val + 1);
return ans;
}
ModInt& operator --() {
val = mod(val - 1);
return *this;
}
ModInt operator --(int) {
ModInt ans(val);
val = mod(val - 1);
return ans;
}
operator int() const {
return (int)val;
}
operator ll() const {
return (ll)val;
}
friend std::ostream& operator <<(std::ostream &stream, const ModInt &x) {
return stream << x.val;
}
friend std::istream& operator >>(std::istream &stream, ModInt &x) {
ll cur;
stream >> cur;
x = ModInt<T, MOD>(cur);
return stream;
}
friend ModInt operator +(ll x, const ModInt &y) {
return ModInt(x) + y;
}
friend ModInt operator -(ll x, const ModInt &y) {
return ModInt(x) - y;
}
friend ModInt operator *(ll x, const ModInt &y) {
return ModInt(x) * y;
}
friend ModInt operator /(ll x, const ModInt &y) {
return ModInt(x) / y;
}
friend ModInt operator +=(ll x, const ModInt &y) {
return ModInt(x) + y;
}
friend ModInt operator -=(ll x, const ModInt &y) {
return ModInt(x) - y;
}
friend ModInt operator *=(ll x, const ModInt &y) {
return ModInt(x) * y;
}
friend ModInt operator /=(ll x, const ModInt &y) {
return ModInt(x) / y;
}
};
const int MOD = (int) 1e9 + 7;
using Mint = ModInt<int, MOD>;
const int MAXN = 200;
Mint dp[MAXN + 1][MAXN + 1][MAXN + 1];
void bkt(int a, int b, int c, bool ok, int id, Mint prd) {
if(a < 0 || b < 0 || c < 0 || prd == 0) return ;
if(id == 3) {
dp[a][b][c] += prd * ok;
return ;
}
else {
int sza = a + c, szb = a + b, szc = b + c;
//cerr << a << " " << b << " " << c << " " << id << "\n";
if(id == 0) {
if(sza == 0) {
bkt(a, b, c, ok, id + 1, prd);
}
else {
bkt(a, b + 1, c - 1, ok, id + 1, prd * (sza - a));
bkt(a - 1, b, c, ok | 1, id + 1, prd * a);
}
}
if(id == 1) {
if(szb == 0) {
bkt(a, b, c, ok, id + 1, prd);
}
else {
bkt(a - 1, b, c + 1, ok, id + 1, prd * (szb - b));
bkt(a, b - 1, c, ok | 1, id + 1, prd * b);
}
}
if(id == 2) {
if(szc == 0) {
bkt(a, b, c, ok, id + 1, prd);
}
else {
bkt(a + 1, b - 1, c, ok, id + 1, prd * (szc - c));
bkt(a, b, c - 1, ok | 1, id + 1, prd * c);
}
}
}
}
int main() {
#ifdef HOME
ifstream cin("A.in");
ofstream cout("A.out");
#endif
int i, j, n, t;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> t;
while(t--) {
vector < vector <int> > fr(3, vector <int>(3 * n));
for(j = 0; j < 3; j++) {
for(i = 0; i < 2 * n; i++) {
int x;
cin >> x;
x--;
fr[j][x]++;
}
}
vector <int> comm(3);
for(j = 0; j < 3; j++) {
for(i = 0; i < 3 * n; i++) {
comm[j] += (fr[j][i] & fr[(j + 1) % 3][i]);
}
}
for(int a = 0; a <= 2 * n; a++) {
for(int b = 0; b <= 2 * n; b++) {
for(int c = 0; c <= 2 * n; c++) {
dp[a][b][c] = 0;
}
}
}
dp[comm[0]][comm[1]][comm[2]] = 1;
for(int sum = comm[0] + comm[1] + comm[2]; sum > 0; sum--) {
for(int a = 0; a <= 2 * n; a++) {
for(int b = 0; b <= 2 * n; b++) {
int c = sum - a - b;
if(c < 0 || c > 2 * n || dp[a][b][c] == 0) continue;
bkt(a, b, c, 0, 0, dp[a][b][c]);
}
}
}
cout << dp[0][0][0] << "\n";
}
return 0;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||