Submission #1831359
Source Code Expand
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.8.0"
+/
import std.stdio, std.algorithm, std.range, std.conv;
// import dcomp.foundation, dcomp.scanner;
// import dcomp.modint;
alias Mint = ModInt!(10^^9 + 7);
int main() {
Scanner sc = new Scanner(stdin);
int n;
sc.read(n);
int[][] g = new int[][n];
foreach (i; 1..n) {
int p;
sc.read(p); p--;
g[p] ~= i;
}
int[] sz = new int[n];
Mint[4][][] dp = new Mint[4][][n];
void dfs(int p) {
sz[p] = 1;
foreach (d; g[p]) {
dfs(d);
sz[p] += sz[d];
}
dp[p] = new Mint[4][](sz[p]+1);
auto ndp = dp[p];
ndp[0][0] = Mint(1);
int msz = 1;
foreach (d; g[p]) {
foreach_reverse (kl; 0..msz+sz[d]+1) {
foreach_reverse (fg; 0..4) {
Mint sm = 0;
foreach_reverse (k; 0..msz+1) {
auto l = kl-k;
if (!(0 <= l && l <= sz[d])) continue;
foreach_reverse (f; 0..4) {
if (~fg & f) continue;
auto g = fg^f;
sm += ndp[k][f] * dp[d][l][g];
}
}
ndp[kl][fg] = sm;
}
}
msz += sz[d];
}
// writeln("fl ", p, " ", ndp);
foreach_reverse (i; 0..sz[p]+1) {
ndp[i][0] += ndp[i][1] + ndp[i][2] + ndp[i][3];
if (i) ndp[i][1] = ndp[i-1][1] + ndp[i-1][0];
else ndp[i][1] = Mint(0);
if (i) ndp[i][2] = ndp[i-1][2] + ndp[i-1][0];
else ndp[i][2] = Mint(0);
ndp[i][3] = Mint(0);
}
}
dfs(0);
// writeln(dp.map!(x => x.to!string).join("\n"));
auto fact = factTable!Mint(10000);
Mint ans = 0;
foreach (i; 0..n+1) {
Mint freq = (i % 2) ? Mint(-1) : Mint(1);
ans += freq * dp[0][i][0] * fact[n-i];
}
writeln(ans);
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((ulong(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() const {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((ulong(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/numeric/primitive.d */
// module dcomp.numeric.primitive;
import std.traits;
import std.bigint;
Unqual!T pow(T, U)(T x, U n)
if (!isFloatingPoint!T && (isIntegral!U || is(U == BigInt))) {
return pow(x, n, T(1));
}
Unqual!T pow(T, U, V)(T x, U n, V e)
if ((isIntegral!U || is(U == BigInt)) && is(Unqual!T == Unqual!V)) {
Unqual!T b = x, v = e;
Unqual!U m = n;
while (m) {
if (m & 1) v *= b;
b *= b;
m /= 2;
}
return v;
}
T powMod(T, U, V)(T x, U n, V md)
if (isIntegral!U || is(U == BigInt)) {
T r = T(1);
while (n) {
if (n & 1) r = (r*x)%md;
x = (x*x)%md;
n >>= 1;
}
return r % md;
}
ulong ulongPowMod(U)(ulong x, U n, ulong md)
if (isIntegral!U || is(U == BigInt)) {
// import dcomp.int128;
x %= md;
ulong r = 1;
while (n) {
if (n & 1) {
r = mul128(r, x).mod128(md);
}
x = mul128(x, x).mod128(md);
n >>= 1;
}
return r % md;
}
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]];
}
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/container/stackpayload.d */
// module dcomp.container.stackpayload;
struct StackPayload(T, size_t MIN = 4) {
import core.exception : RangeError;
import std.algorithm : max;
import std.conv;
import std.range.primitives : ElementEncodingType;
import core.stdc.string : memcpy;
private T* _data;
private uint len, cap;
bool empty() const { return len == 0; }
@property size_t length() const { return len; }
alias opDollar = length;
ref inout(T) opIndex(size_t i) inout { return _data[i]; }
ref inout(T) front() inout { return _data[0]; }
ref inout(T) back() inout { assert(len); return _data[len-1]; }
void reserve(size_t nlen) {
import core.memory : GC;
if (nlen <= cap) return;
void* nx = GC.malloc(nlen * T.sizeof);
cap = nlen.to!uint;
if (len) memcpy(nx, _data, len * T.sizeof);
_data = cast(T*)(nx);
}
void free() {
import core.memory : GC;
GC.free(_data);
}
void opOpAssign(string op : "~")(T item) {
if (len == cap) {
reserve(max(MIN, cap*2));
}
_data[len++] = item;
}
void insertBack(T item) {
this ~= item;
}
void removeBack() {
len--;
}
void clear() {
len = 0;
}
inout(T)[] data() inout {
return (_data) ? _data[0..len] : null;
}
static struct RangeT(A) {
import std.traits : CopyTypeQualifiers;
alias E = CopyTypeQualifiers!(A, T);
A *p;
size_t a, b;
@property bool empty() const { return b <= a; }
@property size_t length() const { return b-a; }
@property RangeT save() { return RangeT(p, a, b); }
@property RangeT!(const A) save() const {
return typeof(return)(p, a, b);
}
alias opDollar = length;
@property ref inout(E) front() inout { return (*p)[a]; }
@property ref inout(E) back() inout { return (*p)[b-1]; }
void popFront() {
version(assert) if (empty) throw new RangeError();
a++;
}
void popBack() {
version(assert) if (empty) throw new RangeError();
b--;
}
ref inout(E) opIndex(size_t i) inout { return (*p)[i]; }
RangeT opSlice() { return this.save; }
RangeT opSlice(size_t i, size_t j) {
version(assert) if (i > j || a + j > b) throw new RangeError();
return typeof(return)(p, a+i, a+j);
}
RangeT!(const A) opSlice() const { return this.save; }
RangeT!(const A) opSlice(size_t i, size_t j) const {
version(assert) if (i > j || a + j > b) throw new RangeError();
return typeof(return)(p, a+i, a+j);
}
}
alias Range = RangeT!(StackPayload!T);
alias ConstRange = RangeT!(const StackPayload!T);
alias ImmutableRange = RangeT!(immutable StackPayload!T);
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/ldc/inline.d */
// module dcomp.ldc.inline;
version(LDC) {
pragma(LDC_inline_ir)
R inlineIR(string s, R, P...)(P);
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;
// import dcomp.container.stackpayload;
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 succW() {
import std.range.primitives : empty, front, popFront;
import std.ascii : isWhite;
while (!line.empty && line.front.isWhite) {
line.popFront;
}
return !line.empty;
}
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;
line = lineBuf[];
f.readln(line);
if (!line.length) return false;
}
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 static if (isStaticArray!T) {
foreach (i; 0..T.length) {
bool f = succW();
assert(f);
x[i] = line.parse!E;
}
} else {
StackPayload!E buf;
while (succW()) {
buf ~= line.parse!E;
}
x = buf.data;
}
} 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) {
/*
Copied by https://github.com/dlang/phobos/blob/master/std/algorithm/iteration.d
Copyright: Andrei Alexandrescu 2008-.
License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
*/
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);
}
}
}
}
import core.bitop : popcnt;
static if (!__traits(compiles, popcnt(ulong.max))) {
public import core.bitop : popcnt;
int popcnt(ulong v) {
return popcnt(cast(uint)(v)) + popcnt(cast(uint)(v>>32));
}
}
bool poppar(ulong v) {
v^=v>>1; v^=v>>2;
v&=0x1111111111111111UL;
v*=0x1111111111111111UL;
return ((v>>60) & 1) != 0;
}
T[N] fixed(T, size_t N)(T[N] a) {return a;}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/int128.d */
// module dcomp.int128;
version(LDC) {
// import dcomp.ldc.inline;
}
version(LDC) version(X86_64) {
version = LDC_IR;
}
ulong[2] mul128(ulong a, ulong b) {
ulong[2] res;
version(LDC_IR) {
ulong upper, lower;
inlineIR!(`
%r0 = zext i64 %0 to i128
%r1 = zext i64 %1 to i128
%r2 = mul i128 %r1, %r0
%r3 = trunc i128 %r2 to i64
%r4 = lshr i128 %r2, 64
%r5 = trunc i128 %r4 to i64
store i64 %r3, i64* %2
store i64 %r5, i64* %3`, void)(a, b, &lower, &upper);
return [lower, upper];
} else version(D_InlineAsm_X86_64) {
ulong upper, lower;
asm {
mov RAX, a;
mul b;
mov lower, RAX;
mov upper, RDX;
}
return [lower, upper];
} else {
ulong B = 2UL^^32;
ulong[2] a2 = [a % B, a / B];
ulong[2] b2 = [b % B, b / B];
ulong[4] c;
foreach (i; 0..2) {
foreach (j; 0..2) {
c[i+j] += a2[i] * b2[j] % B;
c[i+j+1] += a2[i] * b2[j] / B;
}
}
foreach (i; 0..3) {
c[i+1] += c[i] / B;
c[i] %= B;
}
return [c[0] + c[1] * B, c[2] + c[3] * B];
}
}
ulong div128(ulong[2] a, ulong b) {
version(LDC_IR) {
return inlineIR!(`
%r0 = zext i64 %0 to i128
%r1 = zext i64 %1 to i128
%r2 = shl i128 %r1, 64
%r3 = add i128 %r0, %r2
%r4 = zext i64 %2 to i128
%r5 = udiv i128 %r3, %r4
%r6 = trunc i128 %r5 to i64
ret i64 %r6`,ulong)(a[0], a[1], b);
} else version(D_InlineAsm_X86_64) {
ulong upper = a[1], lower = a[0];
ulong res;
asm {
mov RDX, upper;
mov RAX, lower;
div b;
mov res, RAX;
}
return res;
} else {
if (b == 1) return a[0];
while (!(b & (1UL << 63))) {
a[1] <<= 1;
if (a[0] & (1UL << 63)) a[1] |= 1;
a[0] <<= 1;
b <<= 1;
}
ulong ans = 0;
foreach (i; 0..64) {
bool up = (a[1] & (1UL << 63)) != 0;
a[1] <<= 1;
if (a[0] & (1UL << 63)) a[1] |= 1;
a[0] <<= 1;
ans <<= 1;
if (up || b <= a[1]) {
a[1] -= b;
ans++;
}
}
return ans;
}
}
ulong mod128(ulong[2] a, ulong b) {
version(D_InlineAsm_X86_64) {
ulong upper = a[1], lower = a[0];
ulong res;
asm {
mov RDX, upper;
mov RAX, lower;
div b;
mov res, RDX;
}
return res;
} else {
return a[0] - div128(a, b) * b;
}
}
/*
This source code generated by dcomp and include dcomp's source code.
dcomp's Copyright: Copyright (c) 2016- Kohei Morita. (https://github.com/yosupo06/dcomp)
dcomp's License: MIT License(https://github.com/yosupo06/dcomp/blob/master/LICENSE.txt)
*/
Submission Info
Submission Time
2017-12-04 04:10:25+0900
Task
A - Awkward
User
yosupo
Language
D (LDC 0.17.0)
Score
0
Code Size
16683 Byte
Status
TLE
Exec Time
3155 ms
Memory
35836 KB
Compile Error
warning: Linking two modules of different data layouts: '<string>' is '' whereas './Main.d' is 'e-m:e-i64:64-f80:128-n8:16:32:64-S128'
warning: Linking two modules of different data layouts: '<string>' is '' whereas './Main.d' is 'e-m:e-i64:64-f80:128-n8:16:32:64-S128'
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 1000
Status
Set Name
Test Cases
Sample
a01, a02, a03, a04
All
a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45, b46, b47, b48, b49, b50, b51, b52, b53, b54, b55
Case Name
Status
Exec Time
Memory
a01
AC
1 ms
380 KB
a02
AC
1 ms
380 KB
a03
AC
1 ms
380 KB
a04
AC
1 ms
380 KB
b05
AC
1 ms
320 KB
b06
TLE
3155 ms
508 KB
b07
AC
270 ms
35836 KB
b08
AC
131 ms
1020 KB
b09
AC
144 ms
764 KB
b10
AC
153 ms
764 KB
b11
AC
220 ms
636 KB
b12
AC
386 ms
636 KB
b13
TLE
3046 ms
636 KB
b14
TLE
3155 ms
508 KB
b15
AC
132 ms
3068 KB
b16
AC
46 ms
508 KB
b17
AC
2 ms
380 KB
b18
AC
1 ms
380 KB
b19
AC
137 ms
892 KB
b20
AC
172 ms
2684 KB
b21
AC
158 ms
764 KB
b22
AC
174 ms
892 KB
b23
AC
1002 ms
636 KB
b24
AC
284 ms
764 KB
b25
AC
224 ms
3196 KB
b26
TLE
3155 ms
508 KB
b27
AC
252 ms
11260 KB
b28
TLE
3155 ms
508 KB
b29
AC
236 ms
28156 KB
b30
AC
238 ms
27004 KB
b31
AC
232 ms
20476 KB
b32
AC
267 ms
34428 KB
b33
AC
149 ms
1020 KB
b34
AC
167 ms
2812 KB
b35
AC
156 ms
4220 KB
b36
AC
278 ms
764 KB
b37
AC
289 ms
2684 KB
b38
AC
140 ms
1020 KB
b39
AC
187 ms
1020 KB
b40
AC
176 ms
892 KB
b41
AC
190 ms
2684 KB
b42
AC
302 ms
764 KB
b43
AC
241 ms
764 KB
b44
AC
383 ms
892 KB
b45
AC
339 ms
33916 KB
b46
AC
279 ms
34684 KB
b47
AC
269 ms
35580 KB
b48
AC
270 ms
35708 KB
b49
AC
270 ms
35708 KB
b50
TLE
3155 ms
508 KB
b51
TLE
3155 ms
508 KB
b52
TLE
3155 ms
2556 KB
b53
TLE
3155 ms
508 KB
b54
TLE
3155 ms
508 KB
b55
AC
194 ms
18684 KB