Submission #1005248
Source Code Expand
#include <cstdio>
#include <cstring>
const int MAXN = 1001;
const int mo = 1e9+7;
typedef long long LL;
struct Matrix
{
int d[2][2];
Matrix()
{
memset(d, 0, sizeof(d));
}
Matrix(int a0, int a1, int a2, int a3)
{
d[0][0] = a0;
d[0][1] = a1;
d[1][0] = a2;
d[1][1] = a3;
}
int* operator [] (const int idx)
{
return d[idx];
}
Matrix operator * (Matrix &s) const
{
Matrix res;
for(int k,j,i=0; i<2; ++i)
for(j=0; j<2; ++j)
for(k=0; k<2; ++k)
res[i][j] = (res[i][j] + LL(d[i][k]) * s[k][j]) % mo;
return res;
}
Matrix operator ^ (LL y) const;
}I(1, 0, 0, 1);
Matrix Matrix::operator ^ (LL y) const
{
Matrix res = I, x = *this;
while (y)
{
if(y&1)
res = res * x;
x = x * x;
y >>= 1;
}
return res;
}
char map[MAXN][MAXN];
int main()
{
int N, M, i, j;
LL K;
scanf("%d%d%lld", &N, &M, &K);
int a = 0, b = 0, c = 0, d = 0, cnt = 0;
for(i=0; i<N; ++i)
{
scanf("%s", map[i]);
for(j=0; j<M; ++j)
if(map[i][j] == '#')
++cnt;
else
map[i][j] = 0;
}
for(i=0; i<N; ++i)
{
if(map[i][0] && map[i][M-1])
++a;
for(j=1; j<M; ++j)
if(map[i][j] && map[i][j-1])
++b;
}
for(j=0; j<M; ++j)
{
if(map[0][j] && map[N-1][j])
++c;
for(i=1; i<N; ++i)
if(map[i][j] && map[i-1][j])
++d;
}
int A, B, C;
if (a && c)
A = 1, B = 0, C = 0;
else if(!a && !c)
A = cnt, B = 0, C = 0;
else if(a && !c)
A = cnt, B = b, C = a;
else
A = cnt, B = d, C = c;
Matrix res = I, s(A, -B, 0, C);
res = res * s ^ (K-1);
printf("%d\n", ((res[0][0] + res[0][1]) % mo + mo) % mo);
}
Submission Info
Submission Time |
|
Task |
F - Fraction of Fractal |
User |
llq |
Language |
C++14 (GCC 5.4.1) |
Score |
1700 |
Code Size |
1644 Byte |
Status |
AC |
Exec Time |
8 ms |
Memory |
1280 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:52:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld", &N, &M, &K);
^
./Main.cpp:56:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", map[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 |
8 ms |
1152 KB |
02.txt |
AC |
8 ms |
1152 KB |
03.txt |
AC |
8 ms |
1152 KB |
04.txt |
AC |
8 ms |
1152 KB |
05.txt |
AC |
8 ms |
1152 KB |
06.txt |
AC |
8 ms |
1152 KB |
07.txt |
AC |
8 ms |
1152 KB |
08.txt |
AC |
7 ms |
1152 KB |
09.txt |
AC |
8 ms |
1152 KB |
10.txt |
AC |
8 ms |
1152 KB |
11.txt |
AC |
7 ms |
1152 KB |
12.txt |
AC |
7 ms |
1152 KB |
13.txt |
AC |
8 ms |
1152 KB |
14.txt |
AC |
7 ms |
1152 KB |
15.txt |
AC |
7 ms |
1152 KB |
16.txt |
AC |
7 ms |
1280 KB |
17.txt |
AC |
8 ms |
1152 KB |
18.txt |
AC |
8 ms |
1152 KB |
19.txt |
AC |
8 ms |
1152 KB |
20.txt |
AC |
8 ms |
1152 KB |
21.txt |
AC |
8 ms |
1152 KB |
22.txt |
AC |
7 ms |
1152 KB |
23.txt |
AC |
7 ms |
1152 KB |
24.txt |
AC |
7 ms |
1152 KB |
25.txt |
AC |
7 ms |
1152 KB |
26.txt |
AC |
7 ms |
1152 KB |
27.txt |
AC |
7 ms |
1152 KB |
28.txt |
AC |
7 ms |
1152 KB |
29.txt |
AC |
1 ms |
128 KB |
30.txt |
AC |
1 ms |
128 KB |
31.txt |
AC |
1 ms |
128 KB |
32.txt |
AC |
1 ms |
128 KB |
33.txt |
AC |
1 ms |
128 KB |
34.txt |
AC |
1 ms |
128 KB |
35.txt |
AC |
1 ms |
128 KB |
36.txt |
AC |
1 ms |
128 KB |
37.txt |
AC |
1 ms |
128 KB |
38.txt |
AC |
1 ms |
128 KB |
39.txt |
AC |
1 ms |
128 KB |
40.txt |
AC |
1 ms |
128 KB |
41.txt |
AC |
1 ms |
128 KB |
42.txt |
AC |
1 ms |
128 KB |
43.txt |
AC |
1 ms |
128 KB |
44.txt |
AC |
1 ms |
128 KB |
s1.txt |
AC |
1 ms |
128 KB |
s2.txt |
AC |
1 ms |
128 KB |
s3.txt |
AC |
1 ms |
128 KB |