Submission #1688113
Source Code Expand
#ifdef DEBUG
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cassert>
#include <sstream>
#include <fstream>
#include <functional>
#include <set>
#include <bitset>
#include <string>
#include <utility>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#else
#include <bits/stdc++.h>
#endif
#ifdef DEBUG
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif
#define rep(i, n) for (int i = 0, i##_end_ = (n); i < i##_end_; ++i)
#define per(i, n) for (int i = (n) - 1; i >= 0; --i)
#define forn(i, l, r) for (int i = (l), i##_end_ = (r); i <= i##_end_; ++i)
#define nrof(i, r, l) for (int i = (r), i##_end_ = (l); i >= i##_end_; --i)
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long LL;
template<typename T> inline bool chkmax(T &x, const T &y) {
return x < y ? x = y, 1 : 0;
}
#ifdef DEBUG
char *input_file, *output_file;
#endif
struct IO {
static const int maxn = (1 << 25) + 10;
char a[maxn], *s, b[maxn], *t;
void INPUT() {
s = a;
t = b;
#ifdef DEBUG
FILE *f = fopen(input_file, "r");
a[fread(a, 1, sizeof a, f)] = 0;
#else
a[fread(a, 1, sizeof a, stdin)] = 0;
#endif
}
void OUTPUT() {
#ifdef DEBUG
FILE *f = fopen(output_file, "w");
fwrite(b, 1, t - b, f);
#else
fwrite(b, 1, t - b, stdout);
#endif
}
operator int() {
int x = 0;
while(*s != '-' && (*s < '0' || *s > '9')) {
++s;
}
bool f = 0;
if(*s == '-') {
f = 1;
++s;
}
while(*s >= '0' && *s <= '9') {
(x *= 10) += *s - '0';
++s;
}
if(f) {
x = -x;
}
return x;
}
operator LL() {
LL x = 0;
while(*s != '-' && (*s < '0' || *s > '9')) {
++s;
}
bool f = 0;
if(*s == '-') {
f = 1;
++s;
}
while(*s >= '0' && *s <= '9') {
(x *= 10) += *s - '0';
++s;
}
if(f) {
x = -x;
}
return x;
}
operator char() {
while(*s != '#' && *s != '.') {
++s;
}
char ret = *s;
++s;
return ret;
}
inline void out(int x) {
if(!x) {
*t++ = '0';
return;
}
if(x < 0) {
*t++ = '-';
x = -x;
}
static char c[20], *i;
i = c;
while(x) {
int y = x / 10;
*i++ = x - y * 10 + '0';
x = y;
}
while(i != c) {
*t++ = *--i;
}
return;
}
inline void out(int x, char C) {
if(!x) {
*t++ = '0';
*t++ = C;
return;
}
if(x < 0) {
*t++ = '-';
x = -x;
}
static char c[20], *i;
i = c;
while(x) {
int y = x / 10;
*i++ = x - y * 10 + '0';
x = y;
}
while(i != c) {
*t++ = *--i;
}
*t++ = C;
return;
}
inline void out(LL x) {
if(!x) {
*t++ = '0';
return;
}
if(x < 0) {
*t++ = '-';
x = -x;
}
static char c[20], *i;
i = c;
while(x) {
LL y = x / 10;
*i++ = x - y * 10 + '0';
x = y;
}
while(i != c) {
*t++ = *--i;
}
return;
}
inline void out(LL x, char C) {
if(!x) {
*t++ = '0';
*t++ = C;
return;
}
if(x < 0) {
*t++ = '-';
x = -x;
}
static char c[20], *i;
i = c;
while(x) {
LL y = x / 10;
*i++ = x - y * 10 + '0';
x = y;
}
while(i != c) {
*t++ = *--i;
}
*t++ = C;
return;
}
inline void out(char c) {
*t++ = c;
return;
}
inline void out(char *s) {
while(*s >= ' ') {
*t++ = *s++;
}
return;
}
}io;
void Main();
int main(int argc, char *argv[]) {
#ifdef DEBUG
input_file = argv[1];
output_file = argv[2];
#endif
io.INPUT();
Main();
io.OUTPUT();
return 0;
}
//---------------------------------------------------------------------------------------head---------------------------------------------------------------------------------------
const int maxn = 1010;
const int mod = 1e9 + 7;
int n, m;
LL K, a, b, c, mat[3][3], ans[3][3];
char s[maxn][maxn], t[maxn][maxn];
int pow_mod(int x, LL n) {
int y = 1;
while(n) {
if(n & 1) {
y = 1ll * y * x % mod;
}
x = 1ll * x * x % mod;
n >>= 1;
}
return y;
}
namespace mul {
LL a[3][3], b[3][3], c[3][3];
void doit() {
memset(c, 0, sizeof c);
rep(i, 3) {
rep(j, 3) {
rep(k, 3) {
c[i][j] = (1ll * a[i][k] * b[k][j] + c[i][j]) % mod;
}
}
}
return;
}
}
bool F(char *s, char *t, int n) {
forn(i, 1, n) {
if(s[i] == '#' && t[i] == '#') {
return 1;
}
}
return 0;
}
void Main() {
n = io;
m = io;
K = io;
if(K <= 1) {
io.out(1, '\n');
return;
}
forn(i, 1, n) {
forn(j, 1, m) {
s[i][j] = io;
}
}
forn(i, 1, n) {
forn(j, 1, m) {
t[j][i] = s[i][j];
}
}
if(F(s[1], s[n], m)) {
if(F(t[1], t[m], n)) {
io.out(1, '\n');
return;
}
else {
exit(-1);
memcpy(s, t, sizeof s);
swap(n, m);
}
}
else {
if(!F(t[1], t[m], n)) {
forn(i, 1, n) {
forn(j, 1, m) {
a += (s[i][j] == '#');
}
}
io.out(pow_mod(a, K), '\n');
return;
}
}
K -= 2;
forn(i, 1, n) {
forn(j, 1, m) {
a += (s[i][j] == '#');
b += (s[i][j] == '#' && s[i][j - 1] == '#');
}
c += (s[i][1] == '#' && s[i][m] == '#');
}
debug("%lld %lld %lld\n", a, b, c);
mat[0][0] = a;
mat[1][1] = a;
mat[1][2] = b;
mat[2][2] = c;
ans[0][0] = ans[1][1] = ans[2][2] = 1;
while(K) {
if(K & 1) {
memcpy(mul::a, ans, sizeof mul::a);
memcpy(mul::b, mat, sizeof mul::b);
mul::doit();
memcpy(ans, mul::c, sizeof mul::a);
}
memcpy(mul::a, mat, sizeof mul::a);
memcpy(mul::b, mat, sizeof mul::b);
mul::doit();
memcpy(mat, mul::c, sizeof mul::a);
K >>= 1;
}
int A = (1ll * ans[0][0] * a + 1ll * ans[0][1] * b + 1ll * ans[0][2] * c) % mod;
int B = (1ll * ans[1][0] * a + 1ll * ans[1][1] * b + 1ll * ans[1][2] * c) % mod;
io.out((A - B + mod) % mod, '\n');
return;
}
Submission Info
Submission Time |
|
Task |
F - Fraction of Fractal |
User |
OMTWOCZWEIXVI |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
6125 Byte |
Status |
RE |
Exec Time |
7 ms |
Memory |
6400 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
6400 KB |
02.txt |
AC |
7 ms |
6400 KB |
03.txt |
RE |
6 ms |
6400 KB |
04.txt |
AC |
7 ms |
6400 KB |
05.txt |
RE |
6 ms |
6400 KB |
06.txt |
WA |
7 ms |
6400 KB |
07.txt |
WA |
7 ms |
6400 KB |
08.txt |
AC |
6 ms |
6400 KB |
09.txt |
AC |
7 ms |
6400 KB |
10.txt |
RE |
6 ms |
6400 KB |
11.txt |
AC |
6 ms |
6400 KB |
12.txt |
AC |
7 ms |
6400 KB |
13.txt |
AC |
7 ms |
6400 KB |
14.txt |
AC |
7 ms |
6400 KB |
15.txt |
AC |
7 ms |
6400 KB |
16.txt |
WA |
7 ms |
6400 KB |
17.txt |
AC |
7 ms |
6400 KB |
18.txt |
AC |
7 ms |
6400 KB |
19.txt |
AC |
7 ms |
6400 KB |
20.txt |
RE |
6 ms |
6400 KB |
21.txt |
RE |
6 ms |
6400 KB |
22.txt |
WA |
7 ms |
6400 KB |
23.txt |
RE |
6 ms |
6400 KB |
24.txt |
RE |
6 ms |
6400 KB |
25.txt |
RE |
6 ms |
6400 KB |
26.txt |
AC |
7 ms |
6400 KB |
27.txt |
RE |
6 ms |
6400 KB |
28.txt |
AC |
7 ms |
6400 KB |
29.txt |
AC |
2 ms |
2304 KB |
30.txt |
AC |
2 ms |
2304 KB |
31.txt |
AC |
2 ms |
2304 KB |
32.txt |
AC |
2 ms |
2304 KB |
33.txt |
AC |
2 ms |
2304 KB |
34.txt |
AC |
2 ms |
2304 KB |
35.txt |
AC |
2 ms |
2304 KB |
36.txt |
AC |
2 ms |
2304 KB |
37.txt |
AC |
2 ms |
2304 KB |
38.txt |
AC |
2 ms |
2304 KB |
39.txt |
AC |
2 ms |
2304 KB |
40.txt |
AC |
2 ms |
2304 KB |
41.txt |
AC |
2 ms |
2304 KB |
42.txt |
AC |
2 ms |
2304 KB |
43.txt |
AC |
2 ms |
2304 KB |
44.txt |
AC |
2 ms |
2304 KB |
s1.txt |
AC |
2 ms |
2304 KB |
s2.txt |
AC |
2 ms |
2304 KB |
s3.txt |
AC |
2 ms |
2304 KB |