結果
問題 |
No.42 貯金箱の溜息
|
ユーザー |
|
提出日時 | 2025-08-09 10:56:33 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 28 ms / 5,000 ms |
コード長 | 4,267 bytes |
コンパイル時間 | 3,487 ms |
コンパイル使用メモリ | 197,028 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-09 10:56:38 |
合計ジャッジ時間 | 4,139 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 |
ソースコード
module main; // https://mayokoex.hatenablog.com/entry/2015/11/13/163505 より // 動的計画法、ラグランジュ補完 import std; struct ModInt(long MOD) { private: long val; public: // コンストラクタ // useMod:MODで剰余を取る処理を行うかどうか this(long x, bool useMod = true) { if (useMod) { val = x % MOD; if (val < 0) val += MOD; } else val = x; } @property long value() const { return val; } @property ModInt value(long x) { val = x % MOD; if (val < 0) val += MOD; return this; } // 代入演算子 ModInt opAssign(T)(T x) if (isIntegral!T) { val = x % MOD; if (val < 0) val += MOD; return this; } // 演算代入演算子 ModInt opOpAssign(string op, T)(T rhs) pure nothrow if (is(T : ModInt) && (op == "+" || op == "-" || op == "*" || op == "/")) { static if (op == "+") { val += rhs.val; while (val >= MOD) val -= MOD; } else static if (op == "-") { val -= rhs.val; while (val < 0) val += MOD; } else static if (op == "*") { val = val * rhs.val % MOD; while (val < 0) val += MOD; } else static if (op == "/") { val = val * rhs.inv().val % MOD; while (val < 0) val += MOD; } return this; } ModInt opOpAssign(string op, T)(T rhs) pure nothrow if (isIntegral!T && (op == "+" || op == "-" || op == "*" || op == "/")) { static if (op == "+") { val += rhs; while (val >= MOD) val -= MOD; } else static if (op == "-") { val -= rhs; while (val < 0) val += MOD; } else static if (op == "*") { val = val * rhs % MOD; while (val < 0) val += MOD; } else static if (op == "/") { val = val * Mint(rhs).inv().val % MOD; while (val < 0) val += MOD; } return this; } // 二項演算子 ModInt opBinary(string op, T)(T rhs) pure nothrow if (is(T : ModInt) && (op == "+" || op == "-" || op == "*" || op == "/")) { auto r = this; return r.opOpAssign!op(rhs); } ModInt opBinary(string op, T)(T rhs) pure nothrow if (isIntegral!T && (op == "+" || op == "-" || op == "*" || op == "/")) { auto r = this; return r.opOpAssign!op(rhs); } ModInt opBinaryRight(string op, T)(T lhs) pure nothrow if (isIntegral!T && (op == "+" || op == "-" || op == "*" || op == "/")) { ModInt r = lhs; return r.opOpAssign!op(this); } // 単項演算子 ModInt opUnary(string op)() pure nothrow if (op == "++" || op == "--") { static if (op == "++") { ++val; if (val == MOD) val = 0; } else static if (op == "--") { if (val == 0) val = MOD; --val; } return this; } ModInt opUnary(string op)() pure const nothrow if (op == "-") { if (val == 0) return Mint(0, false); else return Mint(MOD - val, false); } // 等号演算子 bool opEquals(ref const ModInt rhs) @safe pure const nothrow { return val == rhs.val; } bool opEquals(T)(const T rhs) @safe pure const nothrow if (isIntegral!T) { return val == rhs; } // 累乗 ModInt pow(T)(T n) pure const if (isIntegral!T) { ModInt x = n >= 0 ? this : inv(), r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } // MODに関する逆元 ModInt inv() pure const { long a = val, b = MOD, u = 1, v = 0; while (b) { long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return ModInt(u); } string toString() pure nothrow const { return val.to!string; } // 連想配列のためのハッシュ hash_t toHash() const @safe pure nothrow { // MMIX by Donald Knuth return cast(hash_t)(6_364_136_223_846_793_005L * val + 1_442_695_040_888_963_407L); } } immutable MOD = 10L ^^ 9 + 9, MAXN = 3100; alias Mint = ModInt!MOD; int[] C = [1, 5, 10, 50, 100, 500]; Mint[] dp; void solve(long M) { if (M < MAXN) { writeln(dp[M]); return; } Mint ans = 0; long q = M % 500, m = (M / 500) % MOD; foreach (i; 0 .. 6) { Mint tmp = 1; foreach (j; 0 .. 6) { if (i == j) continue; tmp *= m - j; tmp *= Mint(i - j).inv(); } tmp *= dp[i * 500 + q]; ans += tmp; } writeln(ans); } void main() { // 前処理 dp = new Mint[](MAXN); dp[] = Mint(1); foreach (i; 1 .. 6) foreach (j; C[i] .. MAXN) dp[j] += dp[j - C[i]]; // テストケースの処理 foreach (_; 0 .. readln.chomp.to!int) { auto M = readln.chomp.to!long; solve(M); } }