Submission #2099747

---

Source Code Expand

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long int int64;

const int MOD = (int) 1e9 + 7;
void sadd(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
}
void ssub(int &a, int b)
{
    a -= b;
    if (a < 0) a += MOD;
}
int add(int a, int b)
{
    sadd(a, b);
    return a;
}
int sub(int a, int b)
{
    ssub(a, b);
    return a;
}
int mul(int a, int b)
{
    return (a * 1LL * b) % MOD;
}
int fpow(int x, int n)
{
    if (n == 0) return 1;
    int a = fpow(x, n >> 1);
    a = mul(a, a);
    if (n & 1) a = mul(a, x);
    return a;
}
int rev(int x)
{
    return fpow(x, MOD - 2);
}

int rev2;
int divi2(int a)
{
    return mul(a, rev2);
}

const int N = 2005;
vector <int> ch[N];
int _C[N][N];
int fact[N];

int C(int n, int k)
{
    if (k < 0 || k > n) return 0;
    return _C[n][k];
}

struct Ans
{
    vector <int> dp, dpEnd, dpOnly;

    Ans() : dp({0, 0}), dpEnd({0, 0}), dpOnly({0, 1}) {}

    Ans operator + (const Ans &A) const // root from this
    {
        Ans ans;
        ans.dpOnly[1] = 0;
        ans.dp.resize((int) dp.size() + (int) A.dp.size() - 1, 0);
        ans.dpEnd.resize((int) dpEnd.size() + (int) A.dpEnd.size() - 1, 0);
        ans.dpOnly.resize((int) dpOnly.size() + (int) A.dpOnly.size() - 1, 0);

        for (int i = 1; i < (int) dp.size(); i++)
            for (int j = 1; j < (int) A.dp.size(); j++)
            {
                int ox = dp[i], oEnd = dpEnd[i], oOnly = dpOnly[i], ax = A.dp[j], aEnd = A.dpEnd[j], aOnly = A.dpOnly[j];
                int aAll = add(ax, add(aEnd, aOnly) );
                                
                sadd(ans.dp[i + j], mul(ox, aAll) );
                sadd(ans.dpEnd[i + j], mul(oEnd, aAll) );
                sadd(ans.dpOnly[i + j], mul(oOnly, aAll) );

                sadd(ans.dp[i + j - 1], mul(oEnd, divi2(aEnd) ) );
                sadd(ans.dpEnd[i + j - 1], mul(oOnly, mul(2, aOnly) ) );
                sadd(ans.dpEnd[i + j - 1], mul(oOnly, aEnd) );
                sadd(ans.dp[i + j - 1], mul(oEnd, aOnly) );
            }
        return ans;
    }

    int pvi()
    {
        int ans = 0;
        for (int i = 1; i < (int) dp.size(); i++)
        {
            int cur = add(dp[i], add(dpEnd[i], dpOnly[i] ) );
            cur = mul(cur, fact[i] );
            if ( ( (int) dp.size() - i) % 2) 
                sadd(ans, cur);
            else ssub(ans, cur);
        }
        return ans;
    }
    void eprint(int id)
    {
        eprintf("---\nv = %d\n", id);
        for (int i = 1; i < (int) dp.size(); i++)
        {
            eprintf("%d : dp %d, dpEnd %d, dpOnly %d\n", i, dp[i], dpEnd[i], dpOnly[i] );
        }
    }
};


Ans dfs(int v)
{
    Ans cur = Ans();
    for (int to : ch[v] )
    {
        eprintf("%d -> %d\n", v, to);
//        cur.eprint(10 + v);
        cur = cur + dfs(to);
    }
//    cur.eprint(v);
    return cur;
}


int main(int,  char **)
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    for (int i = 0; i < N; i++)
    {
        _C[i][i] = _C[i][0] = 1;
        for (int j = 1; j < i; j++)
            _C[i][j] = add(_C[i - 1][j], _C[i - 1][j - 1] );
    }
    fact[0] = 1;
    for (int i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);

    rev2 = rev(2);

    int n;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        x--;
        ch[x].push_back(i);
    }

    Ans ans = dfs(0);
    int answer = ans.pvi();
    printf("%d\n", answer);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:166:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:170:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^

Judge Result