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
AC × 3
AC × 27
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