Submission #1046362
Source Code Expand
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
using namespace std;
#ifdef DEB
#define dump(x) cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
template<class T> void
debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif
template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }
typedef long long int lint;
typedef pair<int,int> pi;
namespace std{
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
out<<'('<<a.fr<<','<<a.sc<<')';
return out;
}
}
template<lint mod>
struct Int_{
unsigned x;
unsigned mpow(Int_ a,unsigned k){
Int_ res=1;
while(k){
if(k&1) res=res*a;
a=a*a;
k>>=1;
}
return res.x;
}
unsigned inverse(Int_ a){
return mpow(a,mod-2);
}
Int_(): x(0) { }
Int_(long long sig) {
int sigt=sig%mod;
if(sigt<0) sigt+=mod;
x=sigt;
}
unsigned get() const { return (unsigned)x; }
Int_ &operator+=(Int_ that) { if((x += that.x) >= mod) x -= mod; return *this; }
Int_ &operator-=(Int_ that) { if((x += mod - that.x) >= mod) x -= mod; return *this; }
Int_ &operator*=(Int_ that) { x = (unsigned long long)x * that.x % mod; return *this; }
Int_ &operator=(Int_ that) { x=that.x; return *this;}
Int_ &operator/=(Int_ that) { x=(unsigned long long) x * inverse(that.x)%mod; return *this;}
bool operator==(Int_ that) const { return x==that.x; }
bool operator!=(Int_ that) const { return x!=that.x; }
Int_ operator-() const { return Int_(0)-Int_(*this);}
Int_ operator+(Int_ that) const { return Int_(*this) += that; }
Int_ operator-(Int_ that) const { return Int_(*this) -= that; }
Int_ operator*(Int_ that) const { return Int_(*this) *= that; }
Int_ operator/(Int_ that) const { return Int_(*this) /= that; }
};
namespace std{
template<lint mod>
ostream &operator <<(ostream& out,const Int_<mod>& a){
out<<a.get();
return out;
}
template<lint mod>
istream &operator >>(istream& in,Int_<mod>& a){
in>>a.x;
return in;
}
};
typedef Int_<1000000007> Int;
Int mpow(Int a,lint k){
Int res=1;
while(k){
if(k&1) res=res*a;
a=a*a;
k>>=1;
}
return res;
}
//const int INF=5e8;
char buf[2005][2005],nbuf[2005][2005];
char s[1005][1005],s2[1005][1005];
int h,w;
lint K;
int main(){
cin>>h>>w>>K;
REP(i,h) scanf("%s",s[i]);
int b=0;
REP(i,h) REP(j,w) if(s[i][j]=='#') ++b;
int tate=0,yoko=0;
REP(i,h) if(s[i][0]=='#' && s[i][w-1]=='#') yoko++;
REP(i,w) if(s[0][i]=='#' && s[h-1][i]=='#') tate++;
if(K==0 || K==1){
puts("1");
return 0;
}
--K;
if(tate&&yoko){
puts("1");
return 0;
}
if(!tate && !yoko){
cout<<mpow(b,K)<<endl;
return 0;
}
if(tate && !yoko){
REP(i,h) REP(j,w) s2[j][i]=s[i][j];
swap(h,w);
REP(i,h) REP(j,w) s[i][j]=s2[i][j];
swap(tate,yoko);
}
int adj=0;
REP(i,h) REP(j,w-1) if(s[i][j]=='#' && s[i][j+1]=='#') ++adj;
Int res=mpow(b,K);
Int x=Int(b)/yoko,y=yoko;
Int subt;
if(x.x!=1) subt=((mpow(x,K)-1)/(x-1));
else subt=K;
subt*=mpow(y,K-1)*adj;
res-=subt;
cout<<res<<endl;
/*
int h2=1,w2=1;
buf[0][0]='#';
REP(_,K){
int h3=h2*h,w3=w*w2;
REP(i,h3) REP(j,w3) nbuf[i][j]='.';
REP(i,h2) REP(j,w2) if(buf[i][j]=='#'){
REP(i2,h) REP(j2,w) if(s[i2][j2]=='#') nbuf[i*h+i2][j*w+j2]='#';
}
h2=h3;
w2=w3;
memcpy(buf,nbuf,sizeof(nbuf));
}
dump(solve(h2,w2));
*/
return 0;
}
Submission Info
Submission Time
2016-12-27 15:10:42+0900
Task
F - Fraction of Fractal
User
hogloid
Language
C++14 (GCC 5.4.1)
Score
1700
Code Size
4008 Byte
Status
AC
Exec Time
12 ms
Memory
2176 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:113:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP(i,h) scanf("%s",s[i]);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1700 / 1700
Status
Set Name
Test Cases
Sample
s1.txt, s2.txt, s3.txt
All
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, s1.txt, s2.txt, s3.txt
Case Name
Status
Exec Time
Memory
01.txt
AC
7 ms
1280 KB
02.txt
AC
8 ms
1280 KB
03.txt
AC
12 ms
2176 KB
04.txt
AC
8 ms
1280 KB
05.txt
AC
12 ms
2176 KB
06.txt
AC
7 ms
1280 KB
07.txt
AC
7 ms
1280 KB
08.txt
AC
7 ms
1280 KB
09.txt
AC
8 ms
1280 KB
10.txt
AC
12 ms
2176 KB
11.txt
AC
7 ms
1280 KB
12.txt
AC
8 ms
1280 KB
13.txt
AC
8 ms
1280 KB
14.txt
AC
7 ms
1280 KB
15.txt
AC
7 ms
1280 KB
16.txt
AC
7 ms
1280 KB
17.txt
AC
8 ms
1280 KB
18.txt
AC
8 ms
1280 KB
19.txt
AC
8 ms
1280 KB
20.txt
AC
12 ms
2176 KB
21.txt
AC
12 ms
2176 KB
22.txt
AC
7 ms
1280 KB
23.txt
AC
11 ms
2176 KB
24.txt
AC
11 ms
2176 KB
25.txt
AC
11 ms
2176 KB
26.txt
AC
8 ms
1280 KB
27.txt
AC
11 ms
2176 KB
28.txt
AC
8 ms
1280 KB
29.txt
AC
3 ms
256 KB
30.txt
AC
2 ms
256 KB
31.txt
AC
3 ms
256 KB
32.txt
AC
3 ms
256 KB
33.txt
AC
3 ms
256 KB
34.txt
AC
3 ms
256 KB
35.txt
AC
3 ms
256 KB
36.txt
AC
3 ms
256 KB
37.txt
AC
3 ms
256 KB
38.txt
AC
3 ms
256 KB
39.txt
AC
3 ms
256 KB
40.txt
AC
3 ms
256 KB
41.txt
AC
3 ms
256 KB
42.txt
AC
3 ms
256 KB
43.txt
AC
3 ms
256 KB
44.txt
AC
3 ms
256 KB
s1.txt
AC
3 ms
256 KB
s2.txt
AC
3 ms
256 KB
s3.txt
AC
3 ms
256 KB