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
Submission Time |
|
Task |
F - Fraction of Fractal |
User |
w4yneb0t |
Language |
C++14 (GCC 5.4.1) |
Score |
1700 |
Code Size |
3471 Byte |
Status |
AC |
Exec Time |
81 ms |
Memory |
23808 KB |
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 |
36 ms |
8064 KB |
02.txt |
AC |
39 ms |
8064 KB |
03.txt |
AC |
80 ms |
23680 KB |
04.txt |
AC |
39 ms |
8064 KB |
05.txt |
AC |
80 ms |
23680 KB |
06.txt |
AC |
37 ms |
8064 KB |
07.txt |
AC |
37 ms |
8064 KB |
08.txt |
AC |
37 ms |
8064 KB |
09.txt |
AC |
39 ms |
8064 KB |
10.txt |
AC |
80 ms |
23680 KB |
11.txt |
AC |
37 ms |
8064 KB |
12.txt |
AC |
39 ms |
8064 KB |
13.txt |
AC |
39 ms |
8064 KB |
14.txt |
AC |
40 ms |
8064 KB |
15.txt |
AC |
37 ms |
8064 KB |
16.txt |
AC |
37 ms |
8064 KB |
17.txt |
AC |
39 ms |
8064 KB |
18.txt |
AC |
39 ms |
8064 KB |
19.txt |
AC |
39 ms |
8064 KB |
20.txt |
AC |
81 ms |
23808 KB |
21.txt |
AC |
81 ms |
23808 KB |
22.txt |
AC |
38 ms |
8064 KB |
23.txt |
AC |
80 ms |
23680 KB |
24.txt |
AC |
80 ms |
23808 KB |
25.txt |
AC |
80 ms |
23808 KB |
26.txt |
AC |
39 ms |
8064 KB |
27.txt |
AC |
79 ms |
23680 KB |
28.txt |
AC |
39 ms |
8064 KB |
29.txt |
AC |
4 ms |
256 KB |
30.txt |
AC |
4 ms |
256 KB |
31.txt |
AC |
4 ms |
256 KB |
32.txt |
AC |
4 ms |
256 KB |
33.txt |
AC |
4 ms |
256 KB |
34.txt |
AC |
4 ms |
256 KB |
35.txt |
AC |
4 ms |
256 KB |
36.txt |
AC |
4 ms |
256 KB |
37.txt |
AC |
4 ms |
256 KB |
38.txt |
AC |
4 ms |
256 KB |
39.txt |
AC |
4 ms |
256 KB |
40.txt |
AC |
4 ms |
256 KB |
41.txt |
AC |
4 ms |
256 KB |
42.txt |
AC |
4 ms |
256 KB |
43.txt |
AC |
4 ms |
256 KB |
44.txt |
AC |
4 ms |
256 KB |
s1.txt |
AC |
4 ms |
256 KB |
s2.txt |
AC |
4 ms |
256 KB |
s3.txt |
AC |
4 ms |
256 KB |