Submission #848258

---

Source Code Expand

#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("0"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}

const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;

// Mod int
const int mod = 1000000007;
struct mint;
mint ex(mint a, ll tms);
struct mint {
  ll x;
  mint():x(0){}
  mint(ll x):x((x%mod+mod)%mod){}
  // mint(ll x):x(x){}
  mint& fix() { x = (x%mod+mod)%mod; return *this;}
  mint& operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}
  mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}
  mint& operator*=(const mint& a){ (x*=a.x)%=mod; return *this;}
  mint& operator/=(const mint& a){ (x*=ex(a,mod-2).x)%=mod; return *this;}
  mint operator+(const mint& a)const{ return mint(*this) += a;}
  mint operator-(const mint& a)const{ return mint(*this) -= a;}
  mint operator*(const mint& a)const{ return mint(*this) *= a;}
  mint operator/(const mint& a)const{ return mint(*this) /= a;}
  bool operator<(const mint& a)const{ return x < a.x;}
  bool operator==(const mint& a)const{ return x == a.x;}
};
istream& operator>>(istream&i,mint&a){i>>a.x;return i;}
ostream& operator<<(ostream&o,const mint&a){o<<a.x;return o;}
typedef vector<mint> vm;
mint ex(mint a, ll tms) {
  if(!tms) return 1;
  mint res = ex(a,tms/2);
  res *= res;
  return (tms&1)?res*a:res;
}
struct comb {
  vm f, g;
  comb(){}
  comb(int mx):f(mx+1),g(mx+1) {
    f[0] = 1;
    rrep(i,mx) f[i] = f[i-1]*i;
    g[mx] = ex(f[mx],mod-2);
    for(int i=mx;i>0;i--) g[i-1] = g[i]*i;
  }
  mint c(int a, int b) {
    if (a < b) return 0;
    return f[a]*g[b]*g[a-b];
  }
};
//

// mint f(ll a, ll b, ll n) {
//   n--;
//   mint res = 0;
//   rep(i,n+1) {
//     res += ex(a,i)*ex(b,n-i);
//   }
//   return res;
// }
mint f(ll a, ll b, ll n) {
  if (n == 0) return 0;
  mint res = f(a,b,n/2);
  res = res*(ex(a,n-n/2)+ex(b,n-n/2));
  if (n&1) res += ex(a*b,n/2);
  return res;
}

int main() {
  int h, w;
  scanf("%d%d",&h,&w);
  ll n;
  scanf("%lld",&n);
  if (n <= 1) {
    cout<<1<<endl;
    return 0;
  }
  vector<string> s(h);
  rep(i,h) cin >> s[i];
  int fl = 0;
  rep(i,h) if (s[i][0] == '#' && s[i].back() == '#') fl |= 1;
  rep(i,w) if (s[0][i] == '#' && s.back()[i] == '#') fl |= 2;
  int c = 0;
  rep(i,h)rep(j,w) c += s[i][j] == '#';
  n--; ////////
  mint ans;
  if (fl == 0) {
    ans = ex(c,n);
  } else if (fl == 3) {
    ans = 1;
  } else {
    if (fl == 2) {
      auto ss = s;
      s = vector<string>(w,string(h,'.'));
      rep(i,h)rep(j,w) s[j][i] = ss[i][j];
      swap(h,w);
    }
    int ds = 0, fs = 0;
    rep(i,h) {
      fl = 0;
      int d = 0;
      int pre = 1;
      rep(j,w) {
        if (s[i][j] == '#') {
          d += !pre;
          pre = 0;
        } else pre = 1;
      }
      fl = (s[i][0] == '#' && s[i].back() == '#');
      ds += d; fs += fl;
    }
    ans = ex(c,n);
    mint now = f(c,fs,n)*ds;
    ans -= now;
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:106:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&h,&w);
                      ^
./Main.cpp:108:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&n);
                   ^

Judge Result