Submission #1088850
Source Code Expand
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.4.0"
+/
import std.stdio, std.range, std.algorithm, std.conv;
// import dcomp.scanner;
// import dcomp.numeric.modint;
// import dcomp.functional;
immutable MD = 10^^9 + 7;
alias Mint = DModInt;
Mint solveBase(int all, int one, int k) {
// writeln("solve ", all, " ", one, " ", k);
if (all < 0) return Mint(0, MD);
if (one < 0) return Mint(0, MD);
if (all == 0) {
if (one == 0) return Mint(1, MD);
return Mint(0, MD);
}
Mint ans = Mint(0, MD);
foreach (i; 0..k+1) {
ans += solve(all-k, one-i, k);
}
return ans;
}
memoCont!solveBase solve;
void main() {
auto sc = new Scanner(stdin);
int n, m, k;
sc.read(n, m, k);
solve.init([[-k, n+m], [-k, m], [k-1, k-1]]);
Mint ans = Mint(0, MD);
foreach (zero; iota(n, 0, -(k-1))) {
foreach (one; iota(m, 0, -(k-1))) {
foreach (useO; 1..k) {
ans += solve(zero+one - k, one - useO, k-1);
}
}
}
writeln(ans);
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/functional.d */
// module dcomp.functional;
struct memoCont(alias pred) {
import core.exception : RangeError;
import std.range, std.algorithm, std.conv;
import std.string : join;
import std.traits : ReturnType, ParameterTypeTuple, isIntegral;
import std.typecons : tuple, Tuple;
import std.meta;
alias R = ReturnType!pred;
alias Args = ParameterTypeTuple!pred;
static assert (allSatisfy!(isIntegral, Args));
static immutable N = Args.length;
int[2][N] rng;
int[N] len;
R[] dp;
bool[] used;
void init(int[2][N] rng) {
this.rng = rng;
len = rng[].map!(a => a[1]-a[0]+1).array;
int sz = len.reduce!"a*b";
dp = new R[sz];
used = new bool[sz];
}
R opCall(Args args) {
int idx, base = 1;
foreach (i, v; args) {
version(assert) {
if (v < rng[i][0] || rng[i][1] < v) {
throw new RangeError;
}
}
assert(rng[i][0] <= v && v <= rng[i][1]);
idx += base*(v - rng[i][0]);
base *= len[i];
}
if (used[idx]) return dp[idx];
used[idx] = true;
auto r = pred(args);
dp[idx] = r;
return r;
}
}
unittest {
// import dcomp.numeric.primitive;
// import dcomp.numeric.modint;
alias Mint = ModInt!(10^^9+7);
auto fact = factTable!Mint(100);
auto iFac = invFactTable!Mint(100);
Mint C0(int a, int b) {
if (a < 0 || a < b) return Mint(0);
return fact[a]*iFac[b]*iFac[a-b];
}
struct A {
static memoCont!C1base C1;
static Mint C1base(int a, int b) {
if (a == 0) {
if (b == 0) return Mint(1);
return Mint(0);
}
if (b < 0) return Mint(0);
return C1(a-1, b-1) + C1(a-1, b);
}
}
A.C1.init([[0, 100], [-2, 100]]);
foreach (i; 0..100) {
foreach (j; 0..100) {
assert(C0(i, j) == A.C1(i, j));
}
}
}
/* IMPORT /home/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;
}
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 /home/yosupo/Program/dcomp/source/dcomp/numeric/modint.d */
// module dcomp.numeric.modint;
// import dcomp.numeric.primitive;
struct ModInt(uint MD) if (MD < int.max) {
import std.conv : to;
uint v;
this(int v) {this.v = (long(v)%MD+MD)%MD;}
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;}
}
unittest {
static assert( is(ModInt!(uint(1000000000) * 2))); //not overflow
static assert(!is(ModInt!(uint(1145141919) * 2))); //overflow!
alias Mint = ModInt!(10^^9+7);
// negative check
assert(Mint(-1).v == 10^^9 + 6);
assert(Mint(-1L).v == 10^^9 + 6);
Mint a = 48;
Mint b = Mint.inv(a);
assert(b.v == 520833337);
Mint c = Mint(15);
Mint d = Mint(3);
assert((c/d).v == 5);
}
struct DModInt {
import std.conv : to;
uint MD, v;
this(int v, uint md) {
MD = md;
this.v = ((long(v)%MD+MD)%MD).to!uint;
}
this(long v, uint md) {
MD = md;
this.v = ((v%MD+MD)%MD).to!uint;
}
auto normS(uint x) {return (x<MD)?x:x-MD;}
auto make(uint x) {DModInt m; m.MD = MD; m.v = x; return m;}
auto opBinary(string op:"+")(DModInt r) {
assert(MD == r.MD);
return make(normS(v+r.v));
}
auto opBinary(string op:"-")(DModInt r) {
assert(MD == r.MD);
return make(normS(v+MD-r.v));
}
auto opBinary(string op:"*")(DModInt r) {
assert(MD == r.MD);
return make((long(v)*r.v%MD).to!uint);
}
auto opBinary(string op:"/")(DModInt r) {
assert(MD == r.MD);
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, x.MD)[0], x.MD);
}
string toString() {return v.to!string;}
}
unittest {
immutable MD = 10^^9 + 7;
alias Mint = DModInt;
//negative check
assert(Mint(-1, MD).v == 10^^9 + 6);
assert(Mint(-1L, MD).v == 10^^9 + 6);
Mint a = Mint(48, MD);
Mint b = Mint.inv(a);
assert(b.v == 520833337);
Mint c = Mint(15, MD);
Mint d = Mint(3, MD);
assert((c/d).v == 5);
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/numeric/primitive.d */
// module dcomp.numeric.primitive;
import std.traits;
T pow(T, U)(T x, U n) { return pow(x, n, T(1)); }
T pow(T, U)(T x, U n, T e) {
while (n) {
if (n & 1) e *= x;
x *= x;
n /= 2;
}
return e;
}
unittest {
assert(pow(3, 5) == 243);
assert(pow(3, 5, 2) == 486);
}
T lcm(T)(in T a, in T b) {
import std.numeric : gcd;
return a / gcd(a,b) * b;
}
unittest {
assert(lcm(2, 4) == 4);
assert(lcm(3, 5) == 15);
assert(lcm(1, 1) == 1);
assert(lcm(0, 100) == 0);
}
//a*T[0]+b*T[1]=T[2], T[2]=gcd
//todo: to binary extgcd
T[3] extGcd(T)(in T a, in T b)
if (!isIntegral!T || isSigned!T) //unsignedはNG
{
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]];
}
}
unittest {
import std.numeric : gcd;
foreach (i; 0..100) {
foreach (j; 0..100) {
auto e = extGcd(i, j);
assert(e[2] == gcd(i, j));
assert(e[0] * i + e[1] * j == e[2]);
}
}
}
T[] factTable(T)(size_t length) {
import std.range : take, recurrence;
import std.array : array;
return T(1).recurrence!((a, n) => a[n-1]*T(n)).take(length).array;
}
// optimize
T[] invFactTable(T)(size_t length) {
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) {
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;
}
unittest {
import std.stdio;
// import dcomp.numeric.modint;
alias Mint = ModInt!(10^^9 + 7);
auto r = factTable!Mint(20);
Mint a = 1;
assert(r[0] == Mint(1));
foreach (i; 1..20) {
a *= Mint(i);
assert(r[i] == a);
}
auto p = invFactTable!Mint(20);
foreach (i; 1..20) {
assert((r[i]*p[i]).v == 1);
}
}
Submission Info
Submission Time |
|
Task |
E - Eternal Average |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
1600 |
Code Size |
10744 Byte |
Status |
AC |
Exec Time |
412 ms |
Memory |
211452 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1600 / 1600 |
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, s1.txt, s2.txt, s3.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
2 ms |
256 KB |
02.txt |
AC |
412 ms |
71164 KB |
03.txt |
AC |
2 ms |
256 KB |
04.txt |
AC |
2 ms |
256 KB |
05.txt |
AC |
305 ms |
71036 KB |
06.txt |
AC |
80 ms |
35708 KB |
07.txt |
AC |
3 ms |
380 KB |
08.txt |
AC |
11 ms |
4988 KB |
09.txt |
AC |
216 ms |
72444 KB |
10.txt |
AC |
218 ms |
73084 KB |
11.txt |
AC |
283 ms |
156924 KB |
12.txt |
AC |
339 ms |
211452 KB |
13.txt |
AC |
194 ms |
70396 KB |
14.txt |
AC |
93 ms |
42620 KB |
15.txt |
AC |
184 ms |
67964 KB |
16.txt |
AC |
108 ms |
91900 KB |
17.txt |
AC |
163 ms |
76028 KB |
18.txt |
AC |
99 ms |
43900 KB |
19.txt |
AC |
10 ms |
2428 KB |
20.txt |
AC |
176 ms |
53116 KB |
21.txt |
AC |
2 ms |
256 KB |
22.txt |
AC |
240 ms |
70908 KB |
23.txt |
AC |
163 ms |
58108 KB |
24.txt |
AC |
152 ms |
55804 KB |
s1.txt |
AC |
2 ms |
256 KB |
s2.txt |
AC |
2 ms |
256 KB |
s3.txt |
AC |
3 ms |
764 KB |