Submission #4063573
Source Code Expand
#include <algorithm>
#include <array>
#include <bitset>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
struct BoolName : numpunct<char> {
string t, f;
BoolName (string t = "Yes", string f = "No") : t(t), f(f) {}
string do_truename() const {return t;}
string do_falsename() const {return f;}
};
struct Initializer {
Initializer() {
cin.tie(0);
ios::sync_with_stdio(0);
cout << fixed << setprecision(15) << boolalpha;
cout.imbue(locale(cout.getloc(), new BoolName));
}
} initializer;
template<typename T> istream& operator>>(istream &s, vector<T> &v) {
for (T &t : v) s >> t;
return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
for (const T &t : v) s << t << endl;
return s;
}
void set_bool_name(string t, string f) {
cout.imbue(locale(cout.getloc(), new BoolName(t, f)));
}
template<typename T> bool chmin(T& a, T b) {return a > b ? a = b, true : false;}
template<typename T> bool chmax(T& a, T b) {return a < b ? a = b, true : false;}
template<typename T> void sort(vector<T>& v) {sort(v.begin(), v.end());}
template<typename T> class Addition {
public:
template<typename V> T operator+(const V& v) const {
return T(static_cast<const T&>(*this)) += v;
}
};
template<typename T> class Subtraction {
public:
template<typename V> T operator-(const V& v) const {
return T(static_cast<const T&>(*this)) -= v;
}
};
template<typename T> class Multiplication {
public:
template<typename V> T operator*(const V& v) const {
return T(static_cast<const T&>(*this)) *= v;
}
};
template<typename T> class Division {
public:
template<typename V> T operator/(const V& v) const {
return T(static_cast<const T&>(*this)) /= v;
}
};
template<typename T> class Modulus {
public:
template<typename V> T operator%(const V& v) const {
return T(static_cast<const T&>(*this)) %= v;
}
};
template<typename T> class IndivisibleArithmetic : public Addition<T>, public Subtraction<T>, public Multiplication<T> {};
template<typename T> class Arithmetic : public IndivisibleArithmetic<T>, public Division<T> {};
class Inverse {
private:
int64_t mod;
vector<int64_t> inv;
public:
Inverse() {}
Inverse(int64_t mod, int64_t n = 1000000) : mod(mod), inv(n, 1) {for (int i = 2; i < n; ++i) inv[i] = inv[mod % i] * (mod - mod / i) % mod;}
int64_t operator()(int64_t a) const {
if (a < int(inv.size())) return inv[a];
int64_t b = mod, x = 1, y = 0;
while (b) {
int64_t t = a / b;
swap(a -= t * b, b);
swap(x -= t * y, y);
}
return x < 0 ? x + mod : x;
}
};
int64_t inverse(int64_t n, int64_t mod) {
Inverse inv(mod, 0);
return inv(n);
}
class Mint : public Arithmetic<Mint> {
private:
static int64_t mod;
static Inverse inverse;
int64_t val;
public:
Mint() : val(0) {}
Mint(const int64_t& val) {
this->val = val % mod;
if (this->val < 0) this->val += mod;
}
static void setMod(const int64_t& m) {
mod = m;
inverse = Inverse(m);
}
Mint operator-() const { return Mint(val ? mod - val : 0); }
Mint operator+=(const Mint& m) {
val += m.val;
if (val >= mod) val -= mod;
return *this;
}
Mint operator-=(const Mint& m) {
val -= m.val;
if (val < 0) val += mod;
return *this;
}
Mint operator*=(const Mint& m) {
val *= m.val;
val %= mod;
return *this;
}
Mint operator/=(const Mint& m) {
val *= inverse(m.val);
val %= mod;
return *this;
}
Mint operator++() {return *this += 1;}
Mint operator--() {return *this -= 1;}
template<typename T> Mint operator-(const T& m) { return Arithmetic<Mint>::operator-(m); }
explicit operator char() const { return val; }
explicit operator int() const { return val; }
explicit operator int64_t() const { return val; }
Mint identity() const {return 1;}
};
int64_t Mint::mod = 1000000007;
Inverse Mint::inverse(1000000007);
ostream& operator<<(ostream& os, Mint a) {
os << int64_t(a);
return os;
}
istream& operator>>(istream& is, Mint& a) {
int64_t n;
is >> n;
a = n;
return is;
}
Mint operator+(const int& n, const Mint& m) { return m + n; }
Mint operator-(const int& n, const Mint& m) { return -m + n; }
Mint operator*(const int& n, const Mint& m) { return m * n; }
Mint operator/(const int& n, const Mint& m) { return Mint(n) / m; }
Mint operator+(const int64_t& n, const Mint& m) { return m + n; }
Mint operator-(const int64_t& n, const Mint& m) { return -m + n; }
Mint operator*(const int64_t& n, const Mint& m) { return m * n; }
Mint operator/(const int64_t& n, const Mint& m) { return Mint(n) / m; }
int main() {
int n;
string s[2];
cin >> n >> s[0] >> s[1];
vector<vector<vector<Mint>>> dp(n, vector<vector<Mint>>(3, vector<Mint>(3)));
if (s[0][0] == s[1][0]) {
for (int i = 0; i < 3; ++i) dp[0][i][i] = 1;
} else {
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (i != j) dp[0][i][j] = 1;
}
}
}
for (int i = 1; i < n; ++i) {
for (int a = 0; a < 3; ++a) {
for (int b = 0; b < 3; ++b) {
if (s[0][i - 1] == s[1][i - 1]) {
if (a != b) continue;
} else {
if (a == b) continue;
}
for (int x = 0; x < 3; ++x) {
if (s[0][i - 1] == s[0][i]) {
if (a != x) continue;
} else {
if (a == x) continue;
}
for (int y = 0; y < 3; ++y) {
if (s[1][i - 1] == s[1][i]) {
if (b != y) continue;
} else {
if (b == y) continue;
}
if (s[0][i] == s[1][i]) {
if (x != y) continue;
} else {
if (x == y) continue;
}
dp[i][x][y] += dp[i - 1][a][b];
}
}
}
}
}
Mint res = 0;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) res += dp.back()[i][j];
}
cout << res << endl;
}
Submission Info
Submission Time |
|
Task |
D - Coloring Dominoes |
User |
not |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
6139 Byte |
Status |
AC |
Exec Time |
19 ms |
Memory |
8064 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
All |
sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
1.txt |
AC |
18 ms |
8064 KB |
10.txt |
AC |
18 ms |
8064 KB |
11.txt |
AC |
18 ms |
8064 KB |
12.txt |
AC |
18 ms |
8064 KB |
13.txt |
AC |
18 ms |
8064 KB |
14.txt |
AC |
18 ms |
8064 KB |
15.txt |
AC |
19 ms |
8064 KB |
16.txt |
AC |
19 ms |
8064 KB |
17.txt |
AC |
18 ms |
8064 KB |
18.txt |
AC |
19 ms |
8064 KB |
19.txt |
AC |
18 ms |
8064 KB |
2.txt |
AC |
18 ms |
8064 KB |
20.txt |
AC |
18 ms |
8064 KB |
21.txt |
AC |
19 ms |
8064 KB |
22.txt |
AC |
18 ms |
8064 KB |
3.txt |
AC |
19 ms |
8064 KB |
4.txt |
AC |
18 ms |
8064 KB |
5.txt |
AC |
18 ms |
8064 KB |
6.txt |
AC |
18 ms |
8064 KB |
7.txt |
AC |
18 ms |
8064 KB |
8.txt |
AC |
18 ms |
8064 KB |
9.txt |
AC |
18 ms |
8064 KB |
sample1.txt |
AC |
18 ms |
8064 KB |
sample2.txt |
AC |
18 ms |
8064 KB |
sample3.txt |
AC |
18 ms |
8064 KB |