Submission #1831361
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..min(kl+1, msz+1)) {
auto l = kl-k;
if (sz[d] < l) break;
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:14:40+0900
Task
A - Awkward
User
yosupo
Language
D (LDC 0.17.0)
Score
1000
Code Size
16677 Byte
Status
AC
Exec Time
290 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
1000 / 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
320 KB
a03
AC
1 ms
380 KB
a04
AC
1 ms
380 KB
b05
AC
1 ms
320 KB
b06
AC
269 ms
508 KB
b07
AC
290 ms
35836 KB
b08
AC
128 ms
1020 KB
b09
AC
128 ms
764 KB
b10
AC
129 ms
764 KB
b11
AC
130 ms
636 KB
b12
AC
132 ms
636 KB
b13
AC
165 ms
636 KB
b14
AC
269 ms
636 KB
b15
AC
128 ms
1020 KB
b16
AC
34 ms
508 KB
b17
AC
2 ms
380 KB
b18
AC
1 ms
2300 KB
b19
AC
128 ms
892 KB
b20
AC
128 ms
764 KB
b21
AC
128 ms
764 KB
b22
AC
129 ms
892 KB
b23
AC
138 ms
636 KB
b24
AC
130 ms
764 KB
b25
AC
142 ms
3196 KB
b26
AC
269 ms
508 KB
b27
AC
182 ms
11260 KB
b28
AC
268 ms
508 KB
b29
AC
251 ms
28156 KB
b30
AC
251 ms
26748 KB
b31
AC
213 ms
18940 KB
b32
AC
285 ms
34428 KB
b33
AC
128 ms
1020 KB
b34
AC
133 ms
4476 KB
b35
AC
133 ms
2428 KB
b36
AC
129 ms
764 KB
b37
AC
131 ms
764 KB
b38
AC
129 ms
1020 KB
b39
AC
129 ms
1020 KB
b40
AC
128 ms
892 KB
b41
AC
129 ms
892 KB
b42
AC
131 ms
764 KB
b43
AC
131 ms
764 KB
b44
AC
132 ms
892 KB
b45
AC
277 ms
33404 KB
b46
AC
285 ms
35324 KB
b47
AC
289 ms
35580 KB
b48
AC
290 ms
35708 KB
b49
AC
289 ms
35708 KB
b50
AC
262 ms
508 KB
b51
AC
268 ms
508 KB
b52
AC
269 ms
508 KB
b53
AC
269 ms
508 KB
b54
AC
269 ms
508 KB
b55
AC
205 ms
18556 KB