fork download
copy 
  1.     import java.util.*;
  2.     import java.io.*; 
  3.     import java.text.*;
  4.  
  5.     public class Main{
  6.         //SOLUTION BEGIN
  7.         int MXN = 71, cp = 0, mxMask = 0;
  8.         int[] prime, sz, fMask;
  9.         ArrayList<Integer>[] adj = new ArrayList[MXN];
  10.         long[][][] ANS,DP;
  11.         void solve(int TC) throws Exception{
  12.             int n = ni();
  13.             for(int i = 1; i<= n; i++)adj[i] = new ArrayList<>();
  14.             for(int i = 2; i<= n; i++)adj[ni()].add(i);
  15.             //Working with primes.
  16.             //Finding all primes below n/2, since primes above n/2 will not matter as we cannot ever have two childs both with subtree size > n/2
  17.             prime = new int[11];
  18.             for(int i = 2; i<= n/2; i++){
  19.                 boolean pr = true;
  20.                 for(int j = 0; j<cp; j++)pr &= (i%prime[j]!=0);
  21.                 if(pr)prime[cp++] = i;
  22.             }
  23.             //Creating a bitmask on primes. It can be seen that there can be atmost 11 primes.
  24.             mxMask = 1<<cp;sz = new int[MXN];
  25.  
  26.             //Our DP table, table[i][j][mask] denote number of possible ways of distributing j coins in subtree of i (including i)
  27.             //such that all subtrees in this subtree are divisible by primes represented in mask
  28.             ANS = new long[MXN][MXN][mxMask];
  29.  
  30.             fMask = new int[MXN];
  31.             //Stores the mask of each value. If ith bit in fMask[x] is 1, it means that x is divisible by ith prime in prime array.
  32.             //Using this, we can easily check if two number share any prime factor stored in prime array.
  33.             // fMask[x1] & fMask[x2] represent common factors between x1 and x2.
  34.             for(int i = 1; i<= n; i++)
  35.                 for(int j = 0; j< cp; j++)
  36.                     if(i%prime[j]==0)fMask[i] |= 1<<j;
  37.             dfs(1);
  38.             //Final answer is represented by sum{table[1][i][j]} for all 0<=i<=n, 0<=j<mxMask, representding every combination of coin and mask at node 1.
  39.             long ans = 0;
  40.             for(int coin = 0; coin<= sz[1]; coin++)
  41.                 for(int mask = 0; mask< mxMask; mask++)
  42.                     ans = (ans+ANS[1][coin][mask])%mod;
  43.             pn(ans);
  44.         }
  45.  
  46.         void dfs(int u) throws Exception{
  47.             sz[u] = 1;
  48.             if(adj[u].isEmpty()){
  49.                 //If node U is leaf, It will either contain 1 coin or 0 coin. Both ways will always be valid. mask would also be 0.
  50.                 ANS[u][0][0] = ANS[u][1][0] = 1;
  51.             }else{
  52.                 for(int v:adj[u]){
  53.                     dfs(v);//Calculations is made from leaf to root
  54.                     sz[u]+=sz[v];//Subtree size updation
  55.                 }
  56.                 //The 
  57.                 DP = new long[sz[u]+1][sz[u]+1][mxMask];//This table is used for intermediate calculations at a node.
  58.                 //dp[i][j][mask] represent number of ways to put exactly j coins in subtrees of first i children of X. 
  59.  
  60.                 DP[0][0][0] = 1;//It is possible to choose 0 coins in first 0 subtrees such that their mask is 0.
  61.  
  62.                 int maxCoins = 0;//
  63.                 int ind = 0;
  64.                 for(int child:adj[u]){
  65.                     for(int coins = 0; coins<=maxCoins; coins++){ //Iterating over max coins we can have uptil now.
  66.                         for(int mask = 0; mask< mxMask; mask++){//Checking every mask
  67.                             if(DP[ind][coins][mask] == 0)continue;//Skipping irrelevant cases
  68.                             for(int add = 0; add<= sz[child]; add++){//Iterating over number of coins to put in this subtree
  69.  
  70.                                 //If subtree of child is not co-prime to mask1, it will also voilate condition of GCD, thus, has to be skipped.
  71.                                 if((fMask[add]&mask)!=0)continue;
  72.  
  73.                                 //Iterating over submask of complement of mask1.
  74.                                 int comp = (mxMask-1)^mask;
  75.                                 for(int mask2 = comp; ; mask2 = (mask2-1)&comp){
  76.                                     //The main DP transition, 
  77.                                     DP[ind+1][coins+add][mask|mask2] = (DP[ind+1][coins+add][mask|mask2]+DP[ind][coins][mask]*ANS[child][add][mask2])%mod;
  78.                                     if(mask2==0)break;
  79.                                 }
  80.                             }
  81.                         }
  82.                     }
  83.                     //Updating Coin count uptil now
  84.                     maxCoins+=sz[child];
  85.                     ind++;
  86.                 }
  87.                 //For updating ANS table for node u.
  88.                 for(int coins = 0; coins<= maxCoins; coins++){
  89.                     for(int cMask = 0; cMask<mxMask; cMask++){
  90.                         //If coin is not put at Node u
  91.                         ANS[u][coins][cMask|fMask[coins]] = (ANS[u][coins][cMask|fMask[coins]]+DP[ind][coins][cMask])%mod;
  92.                         //If coin is put at node u.
  93.                         ANS[u][coins+1][cMask|fMask[coins+1]] = (ANS[u][coins+1][cMask|fMask[coins+1]]+DP[ind][coins][cMask])%mod;
  94.                     }
  95.                 }
  96.             }
  97.         }
  98.         //SOLUTION ENDS
  99.  
  100.  
  101.         long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
  102.         int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
  103.         int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
  104.         void p(Object o){out.print(o);}
  105.         void pn(Object o){out.println(o);}
  106.         void pni(Object o){out.println(o);out.flush();}
  107.         String n(){return in.next();}
  108.         String nln(){return in.nextLine();}
  109.         int ni(){return Integer.parseInt(in.next());}
  110.         long nl(){return Long.parseLong(in.next());}
  111.         double nd(){return Double.parseDouble(in.next());}
  112.  
  113.         class FastReader{
  114.             BufferedReader br;
  115.             StringTokenizer st;
  116.             public FastReader(){
  117.                 br = new BufferedReader(new InputStreamReader(System.in));
  118.             }
  119.  
  120.             public FastReader(String s) throws Exception{
  121.                 br = new BufferedReader(new FileReader(s));
  122.             }
  123.  
  124.             String next(){
  125.                 while (st == null || !st.hasMoreElements()){
  126.                     try{
  127.                         st = new StringTokenizer(br.readLine());
  128.                     }catch (IOException  e){
  129.                         e.printStackTrace();
  130.                     }
  131.                 }
  132.                 return st.nextToken();
  133.             }
  134.  
  135.             String nextLine(){
  136.                 String str = "";
  137.                 try{    
  138.                     str = br.readLine();
  139.                 }catch (IOException e){
  140.                     e.printStackTrace();
  141.                 }   
  142.                 return str;
  143.             }
  144.         }
  145.         long mod = (int)1e9+7, IINF = (long)1e18;
  146.         final int MAX = (int)1e4+1, INF = (int)1e9, root = 3;
  147.         DecimalFormat df = new DecimalFormat("0.00000000");
  148.         double PI = 3.141592653589793238462643383279502884197169399375105820974944;
  149.         static boolean multipleTC = false, memory = true;
  150.         FastReader in;PrintWriter out;
  151.         public static void main(String[] args) throws Exception{
  152.             if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
  153.             else new Main().run();
  154.         }
  155.         void run() throws Exception{
  156.             in = new FastReader();
  157.             out = new PrintWriter(System.out);
  158.             for(int i = 1, T= (multipleTC)?ni():1; i<= T; i++)solve(i);
  159.             out.flush();
  160.             out.close();
  161.         }
  162.     }
Success #stdin #stdout 0.12s 29484KB
comments (?)
stdin
copy 
5
1 1 2 3
stdout
copy 
30
https://ideone.com/pCnXmc
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!