Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define TRACE(x) x
- #define WATCH(x) TRACE(cout << #x" = " << x << endl)
- #define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
- #define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})
- #define all(x) (x).begin(), (x).end()
- typedef long long ll;
- typedef vector<bool> vb;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<ll> vll;
- typedef vector<vll> vvll;
- struct mll {
- static const int MOD = 1e9 + 9;
- static vector<mll> inv_cache;
- static vector<mll> pow2, ipow2, fact, ifact;
- ll val;
- mll(ll _val = 0) {
- val = _val % MOD;
- if (val < 0) val += MOD;
- }
- #define def(op) \
- mll operator op (const mll &o) const { \
- return mll(val op o.val); \
- }
- def(+) def(-) def(*)
- mll pow(ll e) const {
- if (e == 0) return mll(1);
- if (e & 1) return *this * this->pow(e - 1);
- return (*this * *this).pow(e/2);
- }
- mll inv() const {
- assert(val != 0);
- if (val < inv_cache.size())
- return inv_cache[val];
- return this->pow(MOD - 2);
- }
- mll operator / (const mll &o) const {
- return *this * o.inv();
- }
- static mll ncr(int n, int r) {
- if (r < 0 || r > n) return mll(0);
- return fact[n] * ifact[r] * ifact[n-r];
- }
- static void init(int mval) {
- inv_cache.resize(mval);
- inv_cache[1] = mll(1);
- for (int i = 2; i < mval; i++)
- inv_cache[i] = inv_cache[MOD % i] * mll(-(MOD/i));
- pow2.resize(mval), ipow2.resize(mval);
- pow2[0] = ipow2[0] = mll(0);
- fact.resize(mval), ifact.resize(mval);
- fact[0] = ifact[0] = mll(1);
- for (int i = 1; i < mval; i++) {
- pow2[i] = pow2[i-1] * 2;
- ipow2[i] = ipow2[i-1] * inv_cache[2];
- fact[i] = fact[i-1] * i;
- ifact[i] = ifact[i-1] * inv_cache[i];
- }
- }
- friend ostream& operator<<(ostream &os, mll m) {
- return os << m.val;
- }
- };
- vector<mll> mll::inv_cache;
- vector<mll> mll::pow2, mll::ipow2, mll::fact, mll::ifact;
- template<typename T> struct matrix {
- int N;
- vector<T> dat;
- matrix<T> (int _N, T fill = T(0), T diag = T(0)) {
- N = _N;
- dat.resize(N * N, fill);
- for (int i = 0; i < N; i++)
- (*this)(i, i) = diag;
- }
- T& operator()(int i, int j) {
- return dat[N * i + j];
- }
- matrix<T> operator *(matrix<T> &b){
- matrix<T> r(N);
- for(int i=0; i<N; i++)
- for(int j=0; j<N; j++)
- for(int k=0; k<N; k++)
- r(i, j) = r(i, j) + (*this)(i, k) * b(k, j);
- return r;
- }
- matrix<T> pow(ll expo){
- if(!expo) return matrix<T>(N, T(0), T(1));
- matrix<T> r = (*this * *this).pow(expo/2);
- return expo&1 ? r * *this : r;
- }
- friend ostream& operator<<(ostream &os, matrix<T> &m){
- os << "{";
- for(int i=0; i<m.N; i++){
- if(i) os << "},\n ";
- os << "{";
- for(int j=0; j<m.N; j++){
- if(j) os << ", ";
- os << setw(10) << m(i, j) << setw(0);
- }
- }
- return os << "}}";
- }
- };
- vector<vector<bool>> read(int M, int state) {
- vector<vector<bool>> board(M, vector<bool>(2, false));
- for (int i = 0; i < M; i++) {
- for (int j = 0; j < 2; j++)
- board[i][j] = (state >> (2 * i + j))&1;
- }
- return board;
- }
- const int moves[8][2] = { { 1, 2 }, {1, -2}, {-1, 2}, {-1, -2},
- { 2, 1 }, {2, -1}, {-2, 1}, {-2, -1} };
- bool valid(int M, vector<vector<bool>> &board) {
- for (int i = 0; i < M; i++) {
- for (int j = 0; j < 3; j++) {
- if (!board[i][j]) continue;
- for (int m = 0; m < 8; m++) {
- int ii = i + moves[m][0];
- int jj = j + moves[m][1];
- if (ii < 0 || jj < 0 || ii >= M || jj >= 3) continue;
- if (board[ii][jj]) return false;
- }
- }
- }
- return true;
- }
- bool adj(int M, int s1, int s2) {
- auto b1 = read(M, s1);
- auto b2 = read(M, s2);
- for (int i = 0; i < M; i++) {
- if (b2[i][0] != b1[i][1])
- return false;
- }
- vector<vector<bool>> comb(M, vector<bool>(3));
- for (int i = 0; i < M; i++) {
- comb[i][0] = b1[i][0];
- comb[i][1] = b1[i][1];
- comb[i][2] = b2[i][1];
- }
- return valid(M, comb);
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0), cout.tie(0);
- cout << fixed << setprecision(15);
- int T;
- cin >> T;
- for (int t = 0; t < T; t++) {
- int M, N;
- cin >> M >> N;
- int states = 1 << (2 * M);
- matrix<mll> m(states, 0, 0);
- for (int s1 = 0; s1 < states; s1++) {
- for (int s2 = 0; s2 < states; s2++) {
- if (adj(M, s1, s2))
- m(s1, s2) = m(s1, s2) + 1;
- }
- }
- m = m.pow(N + 2);
- cout << m(0, 0) << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement