Submission #2622193

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

int N, fac[2018], vol[2018], dp[2018][2018][2][3], old[2018][2][3];
const int mod = 1e9 + 7;
vector < int > v[2018];

int add (int x, int y) {int ans = x + y; if (ans >= mod) ans -= mod; return ans;}
int subtract (int x, int y) {if (x >= y) return x - y; return x - y + mod;}
int mul (int x, int y) {return 1LL * x * y % mod;}
void adto (int &x, int y) {x += y; if (x >= mod) x -= mod;}

/*
dp[i][j][parity][0/1/2]

parity of the number of edges chosen to be part of a path
[0/1/2] the number of edges adjacent to i (the root) already chosen
j is the number of different paths (including 1-length ones)?
multiplied by 2^the number of paths of non-zero length that are present already
*/
const int inv2 = (mod + 1) / 2;
void dfs (int nod)
{
    vol[nod] = 1, dp[nod][1][0][0] = 1;
    for (auto it : v[nod])
    {
        dfs (it);
        for (int i=0; i<=vol[nod]; i++)
            for (int j=0; j<2; j++)
                for (int k=0; k<3; k++)
                    old[i][j][k] = dp[nod][i][j][k], dp[nod][i][j][k] = 0;
        for (int i=0; i<=vol[nod]; i++)
            for (int p1=0; p1<2; p1++)
                for (int k1=0; k1<3; k1++)
                    if (old[i][p1][k1])
                        for (int j=0; j<=vol[it]; j++)
                            for (int p2=0; p2<2; p2++)
                                for (int k2=0; k2<3; k2++)
                                    if (dp[it][j][p2][k2])
                                    {
                                        int curr = mul (old[i][p1][k1], dp[it][j][p2][k2]);
                                        for (int e=0; e<2 && e + k2 < 3 && e + k1 < 3; e++)
                                        {
                                            ///e=0/1 whether I chose or not the edge between it and nod
                                            int newSize = i + j - e;
                                            if (k1 > 0 && k2 > 0 && e == 1)
                                                curr = mul (curr, inv2);
                                            if (k1 == 0 && k2 == 0 && e == 1)
                                                curr = add (curr, curr);
                                            adto (dp[nod][newSize][p1 ^ p2 ^ e][e + k1], curr);
                                        }
                                    }
        vol[nod] += vol[it];
    }
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d", &N);
for (int i=2; i<=N; i++)
{
    int t;
    scanf ("%d", &t);
    v[t].push_back (i);
}
dfs (1);
fac[0] = 1;
for (int i=1; i<=N; i++)
    fac[i] = mul (fac[i - 1], i);
int ans = 0;
for (int p=0; p<2; p++)
{
    int curr = 0;
    for (int i=1; i<=N; i++)
        for (int j=0; j<3; j++)
            adto (curr, mul (dp[1][i][p][j], fac[i]));
    if (p == 0) adto (ans, curr);
    else ans = subtract (ans, curr);
}
printf ("%d\n", ans);
return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:63:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &N);
                 ^
./Main.cpp:67:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &t);
                     ^

Judge Result