Submission #847932

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
const in mdl=1000000007LL;
in pmod=mdl;
in p2(in a){
  return (1LL<<a);
}
template<typename T> T pw(T a, in b){
  T r=1;
  for(in i=61;i>=0;i--){
    r*=r;
    if(b&p2(i))
      r*=a;
  }
  return r;
}
struct fp{
  in a;
  fp(in aa=0){
    a=aa;
    if(a<0 || a>=pmod)
      a%=pmod;
    if(a<0)
      a+=pmod;
  }
  fp inv()const{
    return pw(*this,pmod-2);
  }
  fp operator*(const fp cp)const{
    return fp(a*cp.a);
  }
  fp operator+(const fp cp)const{
    return fp((a+cp.a)>pmod?a+cp.a-pmod:a+cp.a);
  }
  fp operator-(const fp cp)const{
    return (*this)+(-cp);
  }
  fp operator-()const{
    return (a==0?0:pmod-a);
  }
  fp& operator*=(const fp cp){
    return (*this)=(*this)*cp;
  }
  fp& operator+=(const fp cp){
    return (*this)=(*this)+cp;
  }
  fp& operator-=(const fp cp){
    return (*this)=(*this)-cp;
  }
};
template<typename T> struct mat{
  vector<vector<T> > a;
  in n,m;
  T ab(T a){
    return a>0?a:-a;
  }
  void ini(in pn, in pm){
    a.clear();
    n=pn;
    m=pm;
    a.resize(n,vector<T>(m,0));
  }
  mat<T> operator*(const mat<T>& cp)const{
    assert(m==cp.n);
    mat r;
    r.ini(n,cp.m);
    forn(i,n){
      forn(j,cp.m){
	forn(k,m){
	  r.a[i][j]+=a[i][k]*cp.a[k][j];
	}
      }
    }
    return r;
  }
  mat<T> operator+(const mat<T>& cp)const{
    assert(n==cp.n && m==cp.m);
    mat r;
    r.ini(n,m);
    forn(i,n){
      forn(j,m){
	r.a[i][j]=a[i][j]+cp.a[i][j];
      }
    }
    return r;
  }
};
template<typename T> mat<T> pwm(mat<T> a, in b){
  mat<T> r;
  assert(a.n==a.m);
  r.ini(a.n,a.m);
  forn(i,a.n)
    r.a[i][i]=1;
  for(in i=62;i>=0;--i){
    r=r*r;
    if(b&p2(i))
      r=r*a;
  }
  return r;
}
typedef mat<fp> mt;
VVI mar,nmar;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n,m,k;
  cin>>n>>m>>k;
  if(k==0){
    cout<<1<<endl;
    return 0;
  }
  mar.resize(n,VI(m));
  char tp;
  forn(i,n){
    forn(j,m){
      cin>>tp;
      assert(tp=='#' || tp=='.');
      mar[i][j]=(tp=='#');
    }
  }
  bool cu=0;
  bool cs=0;
  forn(i,n)
    cs|=(mar[i][0]&&mar[i][m-1]);
  forn(j,m)
    cu|=(mar[0][j]&&mar[n-1][j]);
  if(cu && cs){
    cout<<1<<endl;
    return 0;
  }
  if(!cu && !cs){
    in cc=0;
    forn(i,n){
      forn(j,m)
	cc+=mar[i][j];
    }
    cout<<pw(fp(cc),k-1).a<<endl;
    return 0;
  }
  if(cu){
    swap(n,m);
    nmar=mar;
    mar=VVI(n,VI(m));
    forv(i,mar){
      forv(j,mar[i])
	mar[i][j]=nmar[j][i];
    }
  }
  in sc=0;
  forn(i,n)
    sc+=(mar[i][0] && mar[i][m-1]);
  in cp=0;
  forn(i,n){
    forn(j,m)
      cp+=mar[i][j];
  }
  in nb=0;
  forn(i,n){
    forn(j,m-1)
      nb+=(mar[i][j]&&mar[i][j+1]);
  }
  mt mmat;
  mmat.ini(2,2);
  mmat.a[0][0]=cp;
  mmat.a[0][1]=-nb;
  mmat.a[1][1]=sc;
  mt tv;
  tv.ini(2,1);
  tv.a[0][0]=1;
  tv.a[1][0]=1;
  mmat=pwm(mmat,k-1);
  tv=mmat*tv;
  cout<<tv.a[0][0].a<<endl;
  return 0;
}

Submission Info

Judge Result