結果

問題 No.196 典型DP (1)
ユーザー te-shte-sh
提出日時 2017-05-10 15:19:33
言語 D
(dmd 2.109.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,677 bytes
コンパイル時間 427 ms
コンパイル使用メモリ 139,656 KB
最終ジャッジ日時 2024-11-14 20:00:42
合計ジャッジ時間 1,100 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/format/internal/write.d(143): Error: cannot implicitly convert expression `obj` of type `const(FactorRing!1000000007)` to `int`
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/format/write.d(1239): Error: template instance `std.format.internal.write.formatValueImpl!(LockingTextWriter, FactorRing!1000000007, char)` error instantiating
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/format/write.d(632):        instantiated from here: `formatValue!(LockingTextWriter, FactorRing!1000000007, char)`
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/stdio.d(1759):        instantiated from here: `formattedWrite!(LockingTextWriter, char, FactorRing!1000000007)`
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/stdio.d(4277):        instantiated from here: `write!(FactorRing!1000000007, char)`
Main.d(52):        instantiated from here: `writeln!(FactorRing!1000000007)`

ソースコード

diff #
プレゼンテーションモードにする

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.container; // SList, DList, BinaryHeap
import std.typecons; // Tuple, Nullable, BigFlags
const p = 10^^9 + 7;
alias FactorRing!p mint;
void main()
{
auto rd1 = readln.split, n = rd1[0].to!size_t, k = rd1[1].to!int;
auto ci = new size_t[][](n);
foreach (_; 0..n-1) {
auto rd2 = readln.split.to!(size_t[]), s = rd2[0], t = rd2[1];
ci[s] ~= t;
ci[t] ~= s;
}
auto r = dfs(ci, n), wi = r[1]; ci = r[0];
auto cci = new size_t[](n);
foreach (i, c; ci)
cci[i] = c.length;
auto di = new size_t[](n);
foreach (w; wi)
di[w] = ci[w].map!(c => di[c]).sum + 1;
auto dp1 = new mint[][](n, k+1);
foreach (w; wi) {
auto dp2 = new mint[][](cci[w]+1, k+1);
foreach (d; dp2)
d[0] = mint(1);
auto ds = size_t(0);
foreach (i, c; ci[w]) {
auto dt = ds + di[c];
foreach (m; 1..min(dt, k)+1)
foreach (j; max(0, m.to!int-ds.to!int)..min(m, di[c])+1) {
dp2[i+1][m] += dp2[i][m-j] * dp1[c][j];
}
ds = dt;
}
auto lk = min(di[w]+1, k+1);
dp1[w][0..lk] = dp2[cci[w]][0..lk];
if (k >= di[w])
dp1[w][di[w]] = 1;
}
writeln(dp1[0][k]);
}
auto dfs(size_t[][] ci, size_t n)
{
size_t[] wi;
size_t[][] di = new size_t[][](n);
bool[] bi = new bool[](n);
auto st = new SList!size_t(0);
bi[0] = true;
while (!st.empty) {
auto s = st.front; st.removeFront();
wi ~= s;
foreach (c; ci[s])
if (!bi[c]) {
di[s] ~= c;
st.insertFront(c);
bi[c] = true;
}
}
wi.reverse();
return Tuple!(size_t[][], size_t[])(di, wi);
}
struct FactorRing(int m)
{
long v;
@property int toInt() { return v.to!int; }
alias toInt this;
this(T)(T _v) { v = mod(_v); }
ref FactorRing!m opAssign(int _v)
{
v = mod(_v);
return this;
}
pure auto mod(long _v) const { return _v > 0 ? _v % m : ((_v % m) + m) % m; }
pure auto opBinary(string op: "+")(int rhs) const { return FactorRing!m(v + rhs); }
pure auto opBinary(string op: "-")(int rhs) const { return FactorRing!m(v - rhs); }
pure auto opBinary(string op: "*")(int rhs) const { return FactorRing!m(v * rhs); }
pure auto opBinary(string op)(FactorRing!m rhs) const
if (op == "+" || op == "-" || op == "*") { return opBinary!op(rhs.v); }
auto opOpAssign(string op: "+")(int rhs) { v = mod(v + rhs); }
auto opOpAssign(string op: "-")(int rhs) { v = mod(v - rhs); }
auto opOpAssign(string op: "*")(int rhs) { v = mod(v * rhs); }
auto opOpAssign(string op)(FactorRing!m rhs)
if (op == "+" || op == "-" || op == "*") { return opOpAssign!op(rhs.v); }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0