Submission #3181096


Source Code Expand

using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;
using Debug = System.Diagnostics.Trace;
using SB = System.Text.StringBuilder;
using System.Numerics;
using static System.Math;
using static System.Console;
namespace Program
{
    public class Solver
    {
        Random rnd = new Random();
        public void Solve()
        {
            var n = ri;
            var G = Enumerate(n, x => new List<int>());
            for (int i = 1; i < n; i++)
            {
                var p = ri - 1;
                G[p].Add(i);
            }
            Func<int, int, KeyValuePair<int, long[,]>> dfs = null;
            dfs = (prev, cur) =>
            {
                var size = 1;
                //dp[sz,deg] = sz 個の連結成分からなり、次数が deg
                var ret = new long[2, 3];
                ret[1, 2] = 1;
                foreach (var t in G[cur])
                {
                    var sz = size;
                    var res = dfs(cur, t);
                    size += res.Key;
                    ret = merge(new int[] { sz, res.Key }, ret, res.Value);
                }
                return new KeyValuePair<int, long[,]>(size, ret);
            };
            var dp = dfs(-1, 0).Value;
            long ans = 0;
            var fact = new long[n + 1];
            fact[0] = 1;
            for (int i = 0; i < n; i++)
                fact[i + 1] = fact[i] * (i + 1) % MOD;
            for (int i = 0; i <= n; i++)
                for (int d = 0; d <= 2; d++)
                {
                    Console.WriteLine($"{i} {d} {dp[i, d]}");
                    var v = dp[i, d] * fact[i] % MOD;
                    if (d != 2) v *= 2;
                    if ((n - i) % 2 == 0) ans += v;
                    else ans -= v;
                    ans %= MOD;
                }
            Console.WriteLine((ans + MOD) % MOD);

        }
        const long MOD = (long)1e9 + 7;

        //merge b to a
        long[,] merge(int[] sz, long[,] a, long[,] b)
        {
            var ret = new long[sz[0] + sz[1] + 1, 3];
            for (int i = 0; i <= sz[0]; i++)
                for (int j = 0; j <= sz[1]; j++)
                    for (int d = 0; d <= 2; d++)
                        for (int e = 0; e <= 2; e++)
                        {
                            var add = a[i, d] * b[j, e] % MOD;
                            if (add == 0) continue;
                            //Console.WriteLine($"{i} {j} {d} {e} {u} {v} {a[i, d, u]} {b[j, e, v]}");
                            update(ref ret[i + j, d], add * (e == 2 ? 1 : 2));
                            if (d != 0 && e != 0)
                            {
                                //Console.WriteLine($"@ i:{i} j:{j} d:{d} e:{e} u:{u} v:{v} a:{a[i, d, u]} b:{b[j, e, v]}");
                                update(ref ret[i + j - 1, d - 1], add);
                            }

                        }

            return ret;
        }
        void update(ref long u, long v)
        {
            u += v;
            u %= MOD;
        }

        const long INF = 1L << 60;
        static int[] dx = { -1, 0, 1, 0 };
        static int[] dy = { 0, 1, 0, -1 };
        int ri { get { return sc.Integer(); } }
        long rl { get { return sc.Long(); } }
        double rd { get { return sc.Double(); } }
        string rs { get { return sc.Scan(); } }
        public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());

        static T[] Enumerate<T>(int n, Func<int, T> f)
        {
            var a = new T[n];
            for (int i = 0; i < n; ++i) a[i] = f(i);
            return a;
        }
        static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
    }
}

#region main
static class Ex
{
    static public string AsString(this IEnumerable<char> ie) { return new string(ie.ToArray()); }
    static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ")
    {
        return string.Join(st, ie);
    }
    static public void Main()
    {
        Console.SetOut(new Program.IO.Printer(Console.OpenStandardOutput()) { AutoFlush = false });
        var solver = new Program.Solver();
        solver.Solve();
        Console.Out.Flush();
    }
}
#endregion
#region Ex
namespace Program.IO
{
    using System.IO;
    using System.Text;
    using System.Globalization;

    public class Printer : StreamWriter
    {
        public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
        public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
    }

    public class StreamScanner
    {
        public StreamScanner(Stream stream) { str = stream; }

        public readonly Stream str;
        private readonly byte[] buf = new byte[1024];
        private int len, ptr;
        public bool isEof = false;
        public bool IsEndOfStream { get { return isEof; } }

        private byte read()
        {
            if (isEof) return 0;
            if (ptr >= len)
            {
                ptr = 0;
                if ((len = str.Read(buf, 0, 1024)) <= 0)
                {
                    isEof = true;
                    return 0;
                }
            }
            return buf[ptr++];
        }

        public char Char()
        {
            byte b = 0;
            do b = read(); while ((b < 33 || 126 < b) && !isEof);
            return (char)b;
        }
        public string Scan()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b);
            return sb.ToString();
        }
        public string ScanLine()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b != '\n' && b != 0; b = (char)read()) if (b != '\r') sb.Append(b);
            return sb.ToString();
        }
        public long Long() { return isEof ? long.MinValue : long.Parse(Scan()); }
        public int Integer() { return isEof ? int.MinValue : int.Parse(Scan()); }
        public double Double() { return isEof ? double.NaN : double.Parse(Scan(), CultureInfo.InvariantCulture); }
    }
}

#endregion

Submission Info

Submission Time
Task A - Awkward
User camypaper
Language C# (Mono 4.6.2.0)
Score 0
Code Size 6390 Byte
Status WA
Exec Time 834 ms
Memory 32072 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
WA × 4
WA × 55
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 WA 26 ms 13392 KB
a02 WA 24 ms 11216 KB
a03 WA 23 ms 11216 KB
a04 WA 24 ms 11344 KB
b05 WA 23 ms 11216 KB
b06 WA 700 ms 29276 KB
b07 WA 834 ms 30152 KB
b08 WA 497 ms 13404 KB
b09 WA 451 ms 13404 KB
b10 WA 421 ms 11484 KB
b11 WA 377 ms 13660 KB
b12 WA 374 ms 14300 KB
b13 WA 452 ms 24536 KB
b14 WA 703 ms 29276 KB
b15 WA 496 ms 13404 KB
b16 WA 119 ms 13388 KB
b17 WA 25 ms 13264 KB
b18 WA 22 ms 9296 KB
b19 WA 511 ms 11356 KB
b20 WA 451 ms 11484 KB
b21 WA 426 ms 13532 KB
b22 WA 491 ms 13660 KB
b23 WA 478 ms 18908 KB
b24 WA 421 ms 13916 KB
b25 WA 427 ms 17244 KB
b26 WA 701 ms 27228 KB
b27 WA 518 ms 27484 KB
b28 WA 712 ms 29276 KB
b29 WA 725 ms 29056 KB
b30 WA 724 ms 29028 KB
b31 WA 646 ms 28636 KB
b32 WA 819 ms 29896 KB
b33 WA 549 ms 11484 KB
b34 WA 666 ms 15836 KB
b35 WA 660 ms 17884 KB
b36 WA 540 ms 11996 KB
b37 WA 530 ms 13916 KB
b38 WA 550 ms 13532 KB
b39 WA 557 ms 11612 KB
b40 WA 551 ms 13532 KB
b41 WA 524 ms 11868 KB
b42 WA 536 ms 14044 KB
b43 WA 533 ms 16092 KB
b44 WA 521 ms 14556 KB
b45 WA 796 ms 32072 KB
b46 WA 821 ms 28104 KB
b47 WA 829 ms 28104 KB
b48 WA 832 ms 30152 KB
b49 WA 833 ms 30152 KB
b50 WA 707 ms 31196 KB
b51 WA 705 ms 27228 KB
b52 WA 706 ms 29276 KB
b53 WA 701 ms 29276 KB
b54 WA 704 ms 31324 KB
b55 WA 647 ms 31324 KB