Submission #1519923
Source Code Expand
/+ dub.sdl: name "A" dependency "dcomp" version=">=0.6.0" +/ import std.stdio, std.algorithm, std.range, std.conv, std.paralellism; import std.typecons; // import dcomp.foundation, dcomp.scanner; // import dcomp.modint; alias Mint = ModInt!(10^^9 + 7); Mint[] fact; Mint[] iFac; static this() { fact = factTable!Mint(2_000_100); iFac = invFactTable!Mint(2_000_100); } Mint C(int n, int k) { if (k < 0 || n < k) return Mint(0); return fact[n]*iFac[k]*iFac[n-k]; } Mint X(int x, int y) { return C(x+y, x); } Mint calc(int[2] a, int[2] b, int[2] up) { int[2] dw = [0, 0]; dw[] -= a[]; up[] -= a[]; b[] -= a[]; a = [0, 0]; /* writeln(a, b, dw, up); Mint sm = 0; foreach (y; dw[1]..up[1]) { foreach (x; dw[0]..up[0]) { sm += C(x+y, x) * C(b[1]-y+b[0]-x, b[0]-x); } }*/ Mint buf = X(dw[0], dw[1]) * X(b[0]-dw[0], b[1]-dw[1]); Mint sm = buf; foreach (z; dw[0]+dw[1]+1..up[0]+up[1]-1) { if (z < dw[1]+up[0]) { buf += X(z-dw[1], dw[1]-1) * X(b[0]-(z-dw[1]), b[1]-dw[1]); } else { buf -= X(up[0]-1, z-up[0]) * X(b[0]-up[0], b[1]-(z-up[0])); } if (z < up[1]+dw[0]) { buf += X(dw[0]-1, z-dw[0]) * X(b[0]-dw[0], b[1]-(z-dw[0])); } else { buf -= X(z-up[1], up[1]-1) * X(b[0]-(z-up[1]), b[1]-up[1]); } sm += buf; } // writeln(a, b, dw, up, sm); return sm; } int main() { auto sc = new Scanner(stdin); int[2] p1, p2, p3, p4, p5, p6; sc.read(p1[0], p2[0], p3[0], p4[0], p5[0], p6[0]); sc.read(p1[1], p2[1], p3[1], p4[1], p5[1], p6[1]); auto pb = p3; p1[] -= pb[]; p2[] -= pb[]; p5[] -= pb[]; p6[] -= pb[]; p3[] -= pb[]; p4[] -= pb[] - 1; alias P = Tuple!(int[2], int); P[4] v1, v2; v1[0][1] = 1; v1[0][0] = [p1[0]-1, p1[1]-1]; v1[1][1] = -1; v1[1][0] = [p1[0]-1, p2[1]]; v1[2][1] = -1; v1[2][0] = [p2[0], p1[1]-1]; v1[3][1] = 1; v1[3][0] = [p2[0], p2[1]]; v2[0][1] = 1; v2[0][0] = [p6[0]+1, p6[1]+1]; v2[1][1] = -1; v2[1][0] = [p6[0]+1, p5[1]]; v2[2][1] = -1; v2[2][0] = [p5[0], p6[1]+1]; v2[3][1] = 1; v2[3][0] = [p5[0], p5[1]]; // writeln(v1); // writeln(v2); Mint sm = 0; foreach (x; parallel(v1)) { foreach (y; v2) { sm += calc(x[0], y[0], p4) * Mint(x[1]) * Mint(y[1]); } } writeln(sm); return 0; } /* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/numeric/primitive.d */ // module dcomp.numeric.primitive; import std.traits; T pow(T, U)(T x, U n) if (!isFloatingPoint!T && isIntegral!U) { return pow(x, n, T(1)); } T pow(T, U)(T x, U n, T e) if (isIntegral!U) { while (n) { if (n & 1) e *= x; x *= x; n /= 2; } return e; } T lcm(T)(in T a, in T b) { import std.numeric : gcd; return a / gcd(a,b) * b; } T[3] extGcd(T)(in T a, in T b) if (!isIntegral!T || isSigned!T) { 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]]; } } /* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/scanner.d */ // module dcomp.scanner; class Scanner { import std.stdio : File; 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) { this.f = f; } char[512] lineBuf; char[] line; private bool succ() { import std.range.primitives : empty, front, popFront; import std.ascii : isWhite; while (true) { while (!line.empty && line.front.isWhite) { line.popFront; } if (!line.empty) break; if (f.eof) return false; line = lineBuf[]; f.readln(line); } return true; } private bool readSingle(T)(ref T x) { import std.algorithm : findSplitBefore; import std.string : strip; import std.conv : parse; if (!succ()) return false; static if (isArray!T) { alias E = ElementType!T; static if (isSomeChar!E) { auto r = line.findSplitBefore(" "); x = r[0].strip.dup; line = r[1]; } else { auto buf = line.split.map!(to!E).array; static if (isStaticArray!T) { assert(buf.length == T.length); } x = buf; line.length = 0; } } else { x = line.parse!T; } 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); } } } /* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/foundation.d */ // module dcomp.foundation; static if (__VERSION__ <= 2070) { template fold(fun...) if (fun.length >= 1) { auto fold(R, S...)(R r, S seed) { import std.algorithm : reduce; static if (S.length < 2) { return reduce!fun(seed, r); } else { import std.typecons : tuple; return reduce!fun(tuple(seed), r); } } } } version (X86) static if (__VERSION__ < 2071) { import core.bitop : bsf, bsr, popcnt; int bsf(ulong v) { foreach (i; 0..64) { if (v & (1UL << i)) return i; } return -1; } int bsr(ulong v) { foreach_reverse (i; 0..64) { if (v & (1UL << i)) return i; } return -1; } int popcnt(ulong v) { int c = 0; foreach (i; 0..64) { if (v & (1UL << i)) c++; } return c; } } /* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/modint.d */ // module dcomp.modint; // import dcomp.numeric.primitive; struct ModInt(uint MD) if (MD < int.max) { import std.conv : to; uint v; this(int v) {this(long(v));} this(long v) {this.v = (v%MD+MD)%MD;} static auto normS(uint x) {return (x<MD)?x:x-MD;} static auto make(uint x) {ModInt m; m.v = x; return m;} auto opBinary(string op:"+")(ModInt r) const {return make(normS(v+r.v));} auto opBinary(string op:"-")(ModInt r) const {return make(normS(v+MD-r.v));} auto opBinary(string op:"*")(ModInt r) const {return make((long(v)*r.v%MD).to!uint);} auto opBinary(string op:"/")(ModInt r) const {return this*inv(r);} auto opOpAssign(string op)(ModInt r) {return mixin ("this=this"~op~"r");} static ModInt inv(ModInt x) {return ModInt(extGcd!int(x.v, MD)[0]);} string toString() {return v.to!string;} } struct DModInt(string name) { import std.conv : to; static uint MD; uint v; this(int v) {this(long(v));} this(long v) {this.v = ((v%MD+MD)%MD).to!uint;} static auto normS(uint x) {return (x<MD)?x:x-MD;} static auto make(uint x) {DModInt m; m.MD = MD; m.v = x; return m;} auto opBinary(string op:"+")(DModInt r) const {return make(normS(v+r.v));} auto opBinary(string op:"-")(DModInt r) const {return make(normS(v+MD-r.v));} auto opBinary(string op:"*")(DModInt r) const {return make((long(v)*r.v%MD).to!uint);} auto opBinary(string op:"/")(DModInt r) const {return this*inv(r);} auto opOpAssign(string op)(DModInt r) {return mixin ("this=this"~op~"r");} static DModInt inv(DModInt x) { return DModInt(extGcd!int(x.v, MD)[0]); } string toString() {return v.to!string;} } template isModInt(T) { const isModInt = is(T : ModInt!MD, uint MD) || is(S : DModInt!S, string s); } T[] factTable(T)(size_t length) if (isModInt!T) { import std.range : take, recurrence; import std.array : array; return T(1).recurrence!((a, n) => a[n-1]*T(n)).take(length).array; } T[] invFactTable(T)(size_t length) if (isModInt!T) { import std.algorithm : map, reduce; import std.range : take, recurrence, iota; import std.array : array; auto res = new T[length]; res[$-1] = T(1) / iota(1, length).map!T.reduce!"a*b"; foreach_reverse (i, v; res[0..$-1]) { res[i] = res[i+1] * T(i+1); } return res; } T[] invTable(T)(size_t length) if (isModInt!T) { auto f = factTable!T(length); auto invf = invFactTable!T(length); auto res = new T[length]; foreach (i; 1..length) { res[i] = invf[i] * f[i-1]; } return res; }
Submission Info
Submission Time | |
---|---|
Task | E - Sightseeing Plan |
User | yosupo |
Language | D (LDC 0.17.0) |
Score | 0 |
Code Size | 9186 Byte |
Status | CE |
Compile Error
./Main.d(6): Error: module paralellism is in file 'std/paralellism.d' which cannot be read import path[0] = /opt/ldc/bin/../import/ldc import path[1] = /opt/ldc/bin/../import