Submission #1545844
Source Code Expand
/+ dub.sdl: name "F" dependency "dcomp" version=">=0.6.0" +/ import std.stdio, std.algorithm, std.range, std.conv; // import dcomp.foundation, dcomp.scanner; // import dcomp.functional; // import dcomp.modint; alias Mint = ModInt!(998244353); Mint[] fact, iFac; static this() { fact = factTable!Mint(2_100_000); iFac = invFactTable!Mint(2_100_000); } Mint C(int n, int k) { if (n < k || n < 0) return Mint(0); return fact[n] * iFac[k] * iFac[n-k]; } int main() { auto sc = new Scanner(stdin); int n, m; sc.read(n, m); if (n < m) swap(n, m); /* if (n != m) { writeln("UNKO"); return 0; }*/ Mint ans = Mint(n); Mint sm = 0; foreach (i; 1..m+1) { sm += C(2*i, i) * C((n-i)+(m-i), n-i); } sm /= C(n+m, n) * Mint(2); // writeln(ans, " ", sm, " ", ans + sm); writeln(ans + sm); return 0; } /* IMPORT /home/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; } /* 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; } } /* 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; } 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 /home/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 /home/yosupo/Program/dcomp/source/dcomp/numeric/primitive.d */ // module dcomp.numeric.primitive; import std.traits; import std.bigint; T pow(T, U)(T x, U n) if (!isFloatingPoint!T && (isIntegral!U || is(U == BigInt))) { return pow(x, n, T(1)); } T pow(T, U)(T x, U n, T e) if (isIntegral!U || is(U == BigInt)) { 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 [T(1), T(0), a]; } else { auto e = extGcd(b, a%b); return [e[1], e[0]-a/b*e[1], e[2]]; } }
Submission Info
Submission Time | |
---|---|
Task | F - Yes or No |
User | yosupo |
Language | D (LDC 0.17.0) |
Score | 2000 |
Code Size | 8991 Byte |
Status | AC |
Exec Time | 56 ms |
Memory | 20732 KB |
Judge Result
Set Name | Sample | Partial | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1500 / 1500 | 500 / 500 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt |
Partial | sample_01.txt, sample_02.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_2_01.txt, subtask_2_02.txt, subtask_2_03.txt, subtask_2_04.txt, subtask_2_05.txt, subtask_2_06.txt, subtask_2_07.txt, subtask_2_08.txt, subtask_2_09.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_28.txt, subtask_2_29.txt, subtask_2_30.txt, subtask_2_31.txt, subtask_2_32.txt, subtask_2_33.txt, subtask_2_34.txt, subtask_2_35.txt, subtask_2_36.txt, subtask_2_37.txt, subtask_2_38.txt, subtask_2_39.txt, subtask_2_40.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 44 ms | 17276 KB |
sample_02.txt | AC | 44 ms | 18172 KB |
sample_03.txt | AC | 44 ms | 19324 KB |
sample_04.txt | AC | 44 ms | 18044 KB |
sample_05.txt | AC | 43 ms | 17404 KB |
subtask_1_01.txt | AC | 44 ms | 20092 KB |
subtask_1_02.txt | AC | 44 ms | 19324 KB |
subtask_1_03.txt | AC | 43 ms | 17916 KB |
subtask_1_04.txt | AC | 44 ms | 20348 KB |
subtask_1_05.txt | AC | 44 ms | 18812 KB |
subtask_1_06.txt | AC | 44 ms | 20220 KB |
subtask_1_07.txt | AC | 44 ms | 20348 KB |
subtask_1_08.txt | AC | 44 ms | 19836 KB |
subtask_1_09.txt | AC | 44 ms | 19196 KB |
subtask_1_10.txt | AC | 43 ms | 16764 KB |
subtask_1_11.txt | AC | 44 ms | 18684 KB |
subtask_1_12.txt | AC | 44 ms | 19324 KB |
subtask_1_13.txt | AC | 45 ms | 20220 KB |
subtask_1_14.txt | AC | 45 ms | 20732 KB |
subtask_1_15.txt | AC | 45 ms | 17404 KB |
subtask_1_16.txt | AC | 46 ms | 19196 KB |
subtask_1_17.txt | AC | 46 ms | 17788 KB |
subtask_1_18.txt | AC | 46 ms | 18300 KB |
subtask_1_19.txt | AC | 45 ms | 16764 KB |
subtask_1_20.txt | AC | 46 ms | 18684 KB |
subtask_1_21.txt | AC | 46 ms | 19708 KB |
subtask_1_22.txt | AC | 46 ms | 19580 KB |
subtask_1_23.txt | AC | 45 ms | 17788 KB |
subtask_1_24.txt | AC | 46 ms | 19964 KB |
subtask_1_25.txt | AC | 45 ms | 17532 KB |
subtask_2_01.txt | AC | 43 ms | 17404 KB |
subtask_2_02.txt | AC | 43 ms | 17276 KB |
subtask_2_03.txt | AC | 44 ms | 20348 KB |
subtask_2_04.txt | AC | 55 ms | 18812 KB |
subtask_2_05.txt | AC | 55 ms | 20092 KB |
subtask_2_06.txt | AC | 54 ms | 18172 KB |
subtask_2_07.txt | AC | 55 ms | 18172 KB |
subtask_2_08.txt | AC | 54 ms | 17404 KB |
subtask_2_09.txt | AC | 54 ms | 18940 KB |
subtask_2_10.txt | AC | 54 ms | 19324 KB |
subtask_2_11.txt | AC | 55 ms | 19452 KB |
subtask_2_12.txt | AC | 55 ms | 20732 KB |
subtask_2_13.txt | AC | 54 ms | 19324 KB |
subtask_2_14.txt | AC | 54 ms | 16892 KB |
subtask_2_15.txt | AC | 55 ms | 20732 KB |
subtask_2_16.txt | AC | 54 ms | 17020 KB |
subtask_2_17.txt | AC | 54 ms | 18428 KB |
subtask_2_18.txt | AC | 53 ms | 18300 KB |
subtask_2_19.txt | AC | 52 ms | 18428 KB |
subtask_2_20.txt | AC | 44 ms | 20092 KB |
subtask_2_21.txt | AC | 43 ms | 18172 KB |
subtask_2_22.txt | AC | 44 ms | 19836 KB |
subtask_2_23.txt | AC | 44 ms | 19964 KB |
subtask_2_24.txt | AC | 44 ms | 19708 KB |
subtask_2_25.txt | AC | 44 ms | 18428 KB |
subtask_2_26.txt | AC | 43 ms | 18044 KB |
subtask_2_27.txt | AC | 44 ms | 20476 KB |
subtask_2_28.txt | AC | 44 ms | 19452 KB |
subtask_2_29.txt | AC | 45 ms | 20092 KB |
subtask_2_30.txt | AC | 45 ms | 17020 KB |
subtask_2_31.txt | AC | 48 ms | 17020 KB |
subtask_2_32.txt | AC | 54 ms | 18300 KB |
subtask_2_33.txt | AC | 54 ms | 17148 KB |
subtask_2_34.txt | AC | 55 ms | 20092 KB |
subtask_2_35.txt | AC | 56 ms | 18684 KB |
subtask_2_36.txt | AC | 54 ms | 18684 KB |
subtask_2_37.txt | AC | 48 ms | 18812 KB |
subtask_2_38.txt | AC | 45 ms | 19964 KB |
subtask_2_39.txt | AC | 54 ms | 20732 KB |
subtask_2_40.txt | AC | 46 ms | 19964 KB |