Submission #4194267


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formax=(b);i>=i##formax;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define uniq(v) sort(all(v));v.erase(unique(all(v)), v.end());
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))
#define dout(d) printf("%.12f\n",d)

typedef long long ll;
typedef __int128_t lll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>ostream& operator<<(ostream& o,const pair<T,Y>& p){return o<<"("<<p.fi<<", "<<p.se<<")";}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

const int N = 1e5;
int a_to_i(int (&a)[8]){
  int ret = 0;
  FORR(i, 6, 1) ret = ret * 3 + a[i];
  return ret;
}
void i_to_a(int i, int (&a)[8]){
  FOR(j, 1, 7){
    a[j] = i%3;
    i /= 3;
  }
}
bool is_any_1(int (&a)[8]){
  FOR(j, 1, 7) if(a[j]==1) return true;
  return false;
}
bool is_next_12(int (&a)[8]){
  FOR(j, 1, 6) if(a[j]+a[j+1] == 3) return true;
  return false;
}
bool is_norm_2(int (&a)[8]){
  int c = 0, cc = 0, s = 0;
  bool z = false;
  FOR(i, 0, 8){
    if(a[i] == 2){
      if(z) return false;
      c++;
      s++;
    }else{
      if(a[i]==1 && s) z = true;
      if(c) cc++;
      c = 0;
    }
  }
  if(cc==1 && (s==1 || s==2)) return false;
  return true;
}
int n, h, HH, w;
map<int, int> m;
VV<ll> e, a, t;
void merge(VV<ll> &a, VV<ll> &b){
  FOR(i, 0, n)FOR(j, 0, n){
    t[i][j] = 0;
    FOR(k, 0, n) t[i][j] += a[i][k] * b[k][j] % MOD;
    t[i][j] %= MOD;
  }
  swap(t, a);
}
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> h >> w;
  HH = modPow(3, h, LINF);
  {
    int t[8]={0,0,0,0,0,0,0,0};
    FOR(i, 0, HH){
      i_to_a(i, t);
      if(!is_any_1(t)) continue;
      if(is_next_12(t)) continue;
      if(!is_norm_2(t)) continue;
      m[i] = sz(m);
    }
  }
  n = sz(m);
  {
    e.resize(n); FOR(i, 0, n) e[i] = V<ll>(n, 0);
    a.resize(n); FOR(i, 0, n) a[i] = V<ll>(n, 0);
    t.resize(n); FOR(i, 0, n) t[i] = V<ll>(n, 0);
    FOR(i, 0, n) e[i][i] = 1;
  }
  {
    int t[8]={0,0,0,0,0,0,0,0};
    int g[8]={0,0,0,0,0,0,0,0};
    each(itr, m){
      i_to_a(itr->fi, t);
      FOR(j, 0, bit(h)){
        int _j = j;
        FOR(k, 0, h){
          g[k+1] = -(_j&1);
          _j >>= 1;
        }
        FOR(i, 1, 7) if(t[i] == 1 && g[i] == -1) g[i] = 1;
        if(!is_any_1(g)) continue;
        FOR(i, 1, 6) if(g[i]>0 && g[i+1] == -1) g[i+1] = g[i];
        FOR(i, 1, 6) if(g[7-i]>0 && g[6-i] == -1) g[6-i] = g[7-i];
        int v = 2;
        FOR(i, 1, 7) if(t[i] == 2 && g[i] == 1) v = 1;
        FOR(i, 1, 7) if(t[i] == 2 && g[i] == -1) g[i] = v;
        FOR(i, 1, 6) if(g[i]>0 && g[i+1] == -1) g[i+1] = g[i];
        FOR(i, 1, 6) if(g[7-i]>0 && g[6-i] == -1) g[6-i] = g[7-i];
        v = 0;
        FOR(i, 0, 8){
          if(g[i] == -1){
            v++;
          }else{
            int vv = ((v >= 3) ? 2 : 0);
            while(v){
              g[i-v] = vv;
              v--;
            }
          }
        }
        if(!is_norm_2(g)) FOR(i, 0, 8)if(g[i]==2) g[i]=0;
        _j = a_to_i(g);
        if(m.find(_j) == m.end() || true){
          assert("fail");
        }
        //a[itr->se][m[_j]]++;
      }
    }
  }
  while(w){
    if(w&1) merge(e, a);
    merge(a, a);
    w >>= 1;
  }
  ll ans = 0;
  {
    int t[8]={0,0,0,0,0,0,0,0};
    each(itr, m){
      i_to_a(itr->fi, t);
      if(t[h] == 1) ans += e[m[1]][itr->se];
    }
  }
  cout << ans % MOD << endl;
  return 0;
}

Submission Info

Submission Time
Task S - マス目
User char134217728
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4943 Byte
Status WA
Exec Time 21 ms
Memory 512 KB

Judge Result

Set Name All
Score / Max Score 0 / 7
Status
WA × 8
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 90, 91
Case Name Status Exec Time Memory
00 WA 18 ms 512 KB
01 WA 21 ms 512 KB
02 WA 2 ms 256 KB
03 WA 2 ms 256 KB
04 WA 1 ms 256 KB
05 WA 1 ms 256 KB
90 WA 1 ms 256 KB
91 WA 2 ms 256 KB