Submission #1048877
Source Code Expand
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.1.1"
+/
import std.stdio, std.datetime, std.range, std.algorithm, std.conv;
// import dcomp.scanner;
// import dcomp.matrix;
// import dcomp.numeric;
alias Mint = ModInt!(10^^9 + 7);
int main(string[] argv) {
Scanner sc = new Scanner();
int h, w; long k;
sc.read(h, w, k);
bool[][] g = new bool[][](h, w);
g.each!((i, ref a) {
string s;
sc.read(s);
a.each!((i, ref a)=>(a=(s[i]=='#')));
});
int gc = g.map!(a => a.count(true)).sum.to!int; //# of true
bool fx, fy;
foreach (i; 0..h) {
if (g[i][0] && g[i][w-1]) {
fx = true;
break;
}
}
foreach (i; 0..w) {
if (g[0][i] && g[h-1][i]) {
fy = true;
break;
}
}
if (fx && fy) {
writeln(1);
return 0;
}
if (!fx && !fy) {
writeln(pow(Mint(gc), k-1).v);
return 0;
}
if (fy) {
bool[][] g2 = new bool[][](w, h);
foreach (y; 0..h) {
foreach (x; 0..w) {
g2[x][y] = g[y][x];
}
}
g = g2;
swap(h, w);
}
int ac, bc;
foreach (i; 0..h) {
foreach (j; 0..w-1) {
if (g[i][j] && g[i][j+1]) ac++;
}
if (g[i][0] && g[i][w-1]) bc++;
}
auto mt = SMatrix!(Mint, 2, 2)();
//gc, nei
mt[0, 0] = Mint(gc);
mt[0, 1] = Mint(0);
//nei = ac * gc + bc * nei
mt[1, 0] = Mint(ac);
mt[1, 1] = Mint(bc);
auto ve = SMatrix!(Mint, 2, 1)();
ve[0, 0] = Mint(1);
ve[1, 0] = Mint(0);
ve = pow(mt, k-1, matrix!(2, 2, (i, j)=>(Mint(i==j ? 1 : 0)))) * ve;
writeln((ve[0,0]-ve[1,0]).v);
return 0;
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;
class Scanner {
import std.stdio : File, stdin;
import std.conv : to;
import std.range : front, popFront, array, ElementType;
import std.array : split;
import std.traits : isSomeChar, isStaticArray, isArray;
import std.algorithm : map;
File f;
this(File f = stdin) {
this.f = f;
}
string[] buf;
private bool succ() {
while (!buf.length) {
if (f.eof) return false;
buf = f.readln.split;
}
return true;
}
private bool readSingle(T)(ref T x) {
if (!succ()) return false;
static if (isArray!T) {
alias E = ElementType!T;
static if (isSomeChar!E) {
//string or char[10] etc
x = buf.front;
buf.popFront;
} else {
static if (isStaticArray!T) {
//static
assert(buf.length == T.length);
}
x = buf.map!(to!E).array;
buf.length = 0;
}
} else {
x = buf.front.to!T;
buf.popFront;
}
return true;
}
int read(T, Args...)(ref T x, auto ref Args args) {
if (!readSingle(x)) return 0;
static if (args.length == 0) {
return 1;
} else {
return 1 + read(args);
}
}
}
unittest {
import std.path : buildPath;
import std.file : tempDir;
import std.algorithm : equal;
import std.stdio : File;
string fileName = buildPath(tempDir, "kyuridenanmaida.txt");
auto fout = File(fileName, "w");
fout.writeln("1 2 3");
fout.writeln("ab cde");
fout.writeln("1.0 1.0 2.0");
fout.close;
Scanner sc = new Scanner(File(fileName, "r"));
int a;
int[2] b;
char[2] c;
string d;
double e;
double[] f;
sc.read(a, b, c, d, e, f);
assert(a == 1);
assert(equal(b[], [2, 3]));
assert(equal(c[], "ab"));
assert(equal(d, "cde"));
assert(e == 1.0);
assert(equal(f, [1.0, 2.0]));
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/numeric.d */
// module dcomp.numeric;
T pow(T, U)(T x, U n, T e) {
while (n) {
if (n & 1) e = e*x;
x = x*x;
n /= 2;
}
return e;
}
T pow(T, U)(T x, U n) {
return pow(x, n, T(1));
}
T lcm(T)(in T a, in T b) {
import std.numeric : gcd, abs;
return a / gcd(a,b) * b;
}
//a*T[0]+b*T[1]=T[2], T[2]=gcd
//todo: to binary extgcd
T[3] extGcd(T)(T a, T b) {
if (b==0) {
return [1, 0, a];
} else {
auto e = extGcd(b, a%b);
return [e[1], e[0]-a/b*e[1], e[2]];
}
}
struct ModInt(uint MD) {
import std.conv : to;
uint v;
this(int v) {this.v = (v%MD+MD)%MD;}
this(long v) {this.v = (v%MD+MD)%MD;}
auto normS(uint x) {return (x<MD)?x:x-MD;}
auto make(uint x) {ModInt m; m.v = x; return m;}
auto opBinary(string op:"+")(ModInt r) {return make(normS(v+r.v));}
auto opBinary(string op:"-")(ModInt r) {return make(normS(v+MD-r.v));}
auto opBinary(string op:"*")(ModInt r) {return make((v.to!long*r.v%MD).to!uint);}
auto opBinary(string op:"/")(ModInt r) {return this*inv(r);}
auto opOpAssign(string op)(ModInt r) {return mixin ("this=this"~op~"r");}
static ModInt inv(ModInt x) {return ModInt(extGcd(x.v, MD)[0]);}
string toString() {return v.to!string;}
}
// f([10]) = [1*]
// &演算での畳み込みを内積に変換する
T[] zeta(T)(T[] v, bool rev) {
import core.bitop : bsr;
int n = bsr(v.length);
assert(1<<n == v.length);
foreach (fe; 0..n) {
foreach (i, _; v) {
if (i & (1<<fe)) continue;
if (!rev) {
v[i] += v[i|(1<<fe)];
} else {
v[i] -= v[i|(1<<fe)];
}
}
}
return v;
}
// xor演算での畳み込みを内積に変換する、サイズ2のFFT
T[] hadamard(T)(T[] v, bool rev) {
import core.bitop : bsr;
int n = bsr(v.length);
assert(1<<n == v.length);
foreach (fe; 0..n) {
foreach (i, _; v) {
if (i & (1<<fe)) continue;
auto l = v[i], r = v[i|(1<<fe)];
if (!rev) {
v[i] = l+r;
v[i|(1<<fe)] = l-r;
} else {
v[i] = (l+r)/2;
v[i|(1<<fe)] = (l-r)/2;
}
}
}
return v;
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/matrix.d */
// module dcomp.matrix;
struct SMatrix(T, size_t H, size_t W) {
T[W][H] data;
@property static size_t height() {return H;}
@property static size_t width() {return W;}
auto ref opIndex(size_t i1, size_t i2) {
return data[i1][i2];
}
auto opBinary(string op:"+", R)(R r)
if(height == R.height && width == R.width) {
auto res = this;
foreach (y; 0..height) foreach (x; 0..W) res[y, x] += r[y, x];
return res;
}
auto opBinary(string op:"*", R)(R r)
if(width == R.height) {
auto res = SMatrix!(T, height, R.width)();
foreach (y; 0..height) {
foreach (x; 0..R.width) {
foreach (k; 0..width) {
res[y, x] += this[y, k]*r[k, x];
}
}
}
return res;
}
}
auto matrix(size_t H, size_t W, alias pred)() {
import std.traits : ReturnType;
SMatrix!(typeof(pred(0, 0)), H, W) res;
foreach (y; 0..H) {
foreach (x; 0..W) {
res[y, x] = pred(y, x);
}
}
return res;
}
Submission Info
Submission Time |
|
Task |
F - Fraction of Fractal |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
1700 |
Code Size |
7704 Byte |
Status |
AC |
Exec Time |
22 ms |
Memory |
3580 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 |
15 ms |
2556 KB |
02.txt |
AC |
17 ms |
2556 KB |
03.txt |
AC |
21 ms |
3580 KB |
04.txt |
AC |
17 ms |
2556 KB |
05.txt |
AC |
22 ms |
3580 KB |
06.txt |
AC |
15 ms |
2556 KB |
07.txt |
AC |
15 ms |
2556 KB |
08.txt |
AC |
15 ms |
2556 KB |
09.txt |
AC |
17 ms |
2556 KB |
10.txt |
AC |
22 ms |
3580 KB |
11.txt |
AC |
15 ms |
2556 KB |
12.txt |
AC |
16 ms |
2556 KB |
13.txt |
AC |
17 ms |
2556 KB |
14.txt |
AC |
15 ms |
2556 KB |
15.txt |
AC |
15 ms |
2556 KB |
16.txt |
AC |
15 ms |
2556 KB |
17.txt |
AC |
17 ms |
2556 KB |
18.txt |
AC |
16 ms |
2556 KB |
19.txt |
AC |
17 ms |
2556 KB |
20.txt |
AC |
21 ms |
3580 KB |
21.txt |
AC |
22 ms |
3580 KB |
22.txt |
AC |
15 ms |
2556 KB |
23.txt |
AC |
21 ms |
3580 KB |
24.txt |
AC |
21 ms |
3580 KB |
25.txt |
AC |
21 ms |
3580 KB |
26.txt |
AC |
16 ms |
2556 KB |
27.txt |
AC |
21 ms |
3580 KB |
28.txt |
AC |
16 ms |
2556 KB |
29.txt |
AC |
3 ms |
256 KB |
30.txt |
AC |
2 ms |
256 KB |
31.txt |
AC |
2 ms |
256 KB |
32.txt |
AC |
2 ms |
256 KB |
33.txt |
AC |
2 ms |
256 KB |
34.txt |
AC |
2 ms |
256 KB |
35.txt |
AC |
2 ms |
256 KB |
36.txt |
AC |
2 ms |
256 KB |
37.txt |
AC |
2 ms |
256 KB |
38.txt |
AC |
2 ms |
256 KB |
39.txt |
AC |
3 ms |
256 KB |
40.txt |
AC |
2 ms |
256 KB |
41.txt |
AC |
3 ms |
256 KB |
42.txt |
AC |
2 ms |
256 KB |
43.txt |
AC |
2 ms |
256 KB |
44.txt |
AC |
2 ms |
256 KB |
s1.txt |
AC |
2 ms |
256 KB |
s2.txt |
AC |
2 ms |
256 KB |
s3.txt |
AC |
2 ms |
256 KB |