Submission #1087251
Source Code Expand
#include <bits/stdc++.h> #define LL long long #define INF 0x7FFFFFFF//or 0x3f3f3f3f ? -Wall using namespace std; template<class T> inline void read(T& x) { int f = 1; x = 0; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();} while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} x *= f; } /*============ Header Template ============*/ const int N = 1000 + 5; const int mo = 1000000007; LL n, m, k, cnt; LL row, col; LL a[3][3], t[3][3], c[3][3]; char s[N][N], ss[N][N]; LL pow(LL a, LL b) { LL ans = 1; while (b) { if (b & 1) ans = (ans * a) % mo; a = (a * a) % mo; b >>= 1; } return ans; } void QAQa() { for (int i = 1; i <= 1; i++) for (int j = 1; j <= 2; j++) { c[i][j] = 0; for (int k = 1; k <= 2; k++) (c[i][j] += a[i][k] * t[k][j]) %= mo; } for (int i = 1; i <= 1; i++) for (int j = 1; j <= 2; j++) a[i][j] = c[i][j]; } void QAQt() { for (int i = 1; i <= 2; i++) for (int j = 1; j <= 2; j++) { c[i][j] = 0; for (int k = 1; k <= 2; k++) (c[i][j] += t[i][k] * t[k][j]) %= mo; } for (int i = 1; i <= 2; i++) for (int j = 1; j <= 2; j++) t[i][j] = c[i][j]; } void pow(LL b) { while (b) { if (b & 1) QAQa(); QAQt(); b >>= 1; } } int main() { read(n), read(m), read(k); if (k == 0) while (1); for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1); for (int i = 1; i <= n; i++) if (s[i][1] == '#' && s[i][m] == '#') row++; for (int i = 1; i <= m; i++) if (s[1][i] == '#' && s[n][i] == '#') col++; if (col && row) {printf("1\n"); return 0;} for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (s[i][j] == '#') cnt++; if (!col && !row) {printf("%lld\n", (pow(cnt, k - 1) + mo) % mo); return 0;} if (col) { row = col; swap(n, m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) ss[i][j] = s[j][i]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) s[i][j] = ss[i][j]; } LL tmp = 0; for (int i = 1; i <= n; i++) for (int j = 1; j + 1 <= m; j++) if (s[i][j] == '#' && s[i][j + 1] == '#') tmp++; a[1][1] = 1; a[1][2] = tmp; t[1][1] = cnt; t[1][2] = 0; t[2][1] = -1; t[2][2] = row; pow(k - 1); printf("%lld\n", (a[1][1] + mo) % mo); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Fraction of Fractal |
User | cicada |
Language | C++14 (GCC 5.4.1) |
Score | 1700 |
Code Size | 2316 Byte |
Status | AC |
Exec Time | 12 ms |
Memory | 2176 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:67:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] for (int i = 1; i <= n; i++) scanf("%s", s[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 | 7 ms | 1280 KB |
02.txt | AC | 9 ms | 1280 KB |
03.txt | AC | 12 ms | 2176 KB |
04.txt | AC | 9 ms | 1280 KB |
05.txt | AC | 12 ms | 2176 KB |
06.txt | AC | 8 ms | 1280 KB |
07.txt | AC | 8 ms | 1280 KB |
08.txt | AC | 7 ms | 1280 KB |
09.txt | AC | 9 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 | 9 ms | 1280 KB |
14.txt | AC | 8 ms | 1280 KB |
15.txt | AC | 8 ms | 1280 KB |
16.txt | AC | 8 ms | 1280 KB |
17.txt | AC | 9 ms | 1280 KB |
18.txt | AC | 9 ms | 1280 KB |
19.txt | AC | 9 ms | 1280 KB |
20.txt | AC | 12 ms | 2176 KB |
21.txt | AC | 12 ms | 2176 KB |
22.txt | AC | 8 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 | 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 |