Submission #1030478
Source Code Expand
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define PR pair
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define REP(i, x, y) for(int i = (int)(x); i <= (int)(y); i++)
#define FOR(i, x, y) for(int i = (int)(x); i < (int)(y); i++)
#define PER(i ,x, y) for(int i = (int)(x); i >= (int)(y); i--)
#define CH ch = getchar()
#define Exit(...) printf(__VA_ARGS__), exit(0)
#define dln() fprintf(stderr,"\n")
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef double db;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI > VII;
typedef PR<int,int> PII;
typedef vector<PII> VPI;
const int inf=2e9;
const LL Inf=1e10;
const int P=1e9+7;
const int N=100005;
inline LL IN(){
LL x = 0;
int ch = 0, f = 0;
for (CH; ch != -1 && (ch < 48 || ch > 57); CH) f = (ch == '-');
for (; ch >= 48 && ch <= 57; CH) x = (x << 1) + (x << 3) + ch - '0';
return f ? (-x) : x;
}
template<typename T> inline int chkmin(T &a, const T &b){if(b < a) return a = b, 1; return 0;}
template<typename T> inline int chkmax(T &a, const T &b){if(b > a) return a = b, 1; return 0;}
void renew(int &x, const int &y){
x += y;
if(x >= P) x -= P;
if(x < 0) x += P;
}
int Pow(int x, LL y, int p){
int a = 1;
for (; y; y >>= 1, x = (LL)x * x %p) if(y & 1) a=(LL)a * x%p;
return a;
}
int W, H;
LL K;
int row = 0, col = 0, S, T, V;
char str[1005][1005], rv[1005][1005];
struct mtx{
int v[5][5];
}c, e, trs;
mtx operator *(const mtx &a, const mtx &b){
REP(i, 1, 2) REP(j, 1, 2){
c.v[i][j] = 0;
REP(k, 1, 2) c.v[i][j] = (c.v[i][j] + (LL)a.v[i][k] * b.v[k][j]) % P;
}
return c;
}
int main(){
scanf("%d%d%lld", &W, &H, &K);
if(K == 1){
printf("1\n");
return 0;
}
REP(i, 1, W) scanf("%s", str[i] + 1);
REP(i, 1, W) if(str[i][1] == '#' && str[i][H] == '#') row = 1;
REP(i, 1, H) if(str[1][i] == '#' && str[W][i] == '#') col = 1;
if(row && col){
printf("%d\n", 1);
return 0;
}
if(!row && !col){
int S = 0;
REP(i, 1, W) REP(j, 1, H) if(str[i][j] == '#') S ++;
printf("%d\n", Pow(S, K - 1, P));
return 0;
}
if(col){
REP(i, 1, H) REP(j, 1, W) rv[i][j] = str[j][i];
swap(H, W);
memcpy(str, rv, sizeof str);
}
REP(i, 1, W){
REP(j, 1, H) if(str[i][j] == '#') S ++;
FOR(j, 1, H) if(str[i][j] == '#' && str[i][j + 1] == '#') ++ V;
if(str[i][1] == '#' && str[i][H] == '#') T ++;
}
int res = Pow(S, K - 1, P);
e.v[1][1] = V, e.v[1][2] = T;
trs.v[1][1] = S, trs.v[1][2] = 0, trs.v[2][1] = V, trs.v[2][2] = T;
for(LL t = K - 2; t; t >>= 1, trs = trs * trs) if(t & 1) e = e * trs;
renew(res, -e.v[1][1]);
printf("%d\n", res);
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Fraction of Fractal |
User |
syc19999 |
Language |
C++14 (GCC 5.4.1) |
Score |
1700 |
Code Size |
2963 Byte |
Status |
AC |
Exec Time |
10 ms |
Memory |
2176 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:79:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%lld", &W, &H, &K);
^
./Main.cpp:84:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP(i, 1, W) scanf("%s", str[i] + 1);
^
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 |
6 ms |
1280 KB |
02.txt |
AC |
8 ms |
1280 KB |
03.txt |
AC |
10 ms |
2176 KB |
04.txt |
AC |
8 ms |
1280 KB |
05.txt |
AC |
10 ms |
2176 KB |
06.txt |
AC |
7 ms |
1280 KB |
07.txt |
AC |
7 ms |
1280 KB |
08.txt |
AC |
6 ms |
1280 KB |
09.txt |
AC |
8 ms |
1280 KB |
10.txt |
AC |
10 ms |
2176 KB |
11.txt |
AC |
6 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 |
10 ms |
1280 KB |
18.txt |
AC |
8 ms |
1280 KB |
19.txt |
AC |
8 ms |
1280 KB |
20.txt |
AC |
10 ms |
2176 KB |
21.txt |
AC |
10 ms |
2176 KB |
22.txt |
AC |
7 ms |
1280 KB |
23.txt |
AC |
10 ms |
2176 KB |
24.txt |
AC |
10 ms |
2176 KB |
25.txt |
AC |
10 ms |
2176 KB |
26.txt |
AC |
8 ms |
1280 KB |
27.txt |
AC |
10 ms |
2176 KB |
28.txt |
AC |
8 ms |
1280 KB |
29.txt |
AC |
3 ms |
256 KB |
30.txt |
AC |
3 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 |