fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. public class TreeMovingDiv2
  4. {
  5.    	static PrintWriter out=new PrintWriter(System.out);
  6. 	static long mod=(long)(1e9+7);
  7. 	static ArrayList<Pair>[] al;
  8. 	static long[][][] dp;
  9. 	static int maxn=55;
  10. 	static ArrayList<Integer>[][] tree;
  11. 	static List<Integer> list;
  12. 	static boolean[] v;
  13.  
  14. 	static void dfs(int tree_num,int u,Pair p1)
  15. 	{
  16. 		v[u]=true;list.add(u);
  17.  
  18. 		for(int x:tree[tree_num][u])
  19. 		{
  20. 			if(!v[x])
  21. 			{
  22. 				if((p1.u==u && p1.v==x) || (p1.u==x && p1.v==u))
  23. 				{
  24. 					continue;
  25. 				}
  26.  
  27. 				dfs(tree_num,x,p1);
  28. 			}
  29. 		}
  30. 	}
  31.  
  32. 	static boolean check(int tree_no,Pair p1,Pair p2,int n)
  33. 	{
  34. 		v=new boolean[n];
  35.  
  36. 		for(int i=0;i<n;i++)
  37. 		{
  38. 			if(!v[i])
  39. 			{
  40. 				list=new ArrayList<Integer>();dfs(tree_no,i,p1);
  41.  
  42. 				Collections.sort(list);
  43.  
  44. 				if(Collections.binarySearch(list,p2.u)>=0 && Collections.binarySearch(list,p2.v)>=0)
  45. 				{
  46. 					return false;
  47. 				}
  48. 				break;
  49. 			}
  50. 		}
  51.  
  52. 		return true;
  53. 	}
  54.  
  55. 	static long solve(int i,int j,int k,int m,int n)
  56. 	{
  57. 		if(i==m-1)	
  58. 		{
  59. 			if(check(m-1,al[m-1].get(k),al[m-2].get(j),n))
  60. 			{
  61. 				return 1;
  62. 			}
  63. 			return 0;
  64. 		}
  65.  
  66. 		if(dp[i][j][k]!=-1)
  67. 		{
  68. 			return dp[i][j][k];
  69. 		}
  70.  
  71. 		else
  72. 		{
  73. 			long ret=0;
  74.  
  75. 			for(int x=0;x<=n-2;x++)
  76. 			{
  77.  
  78. 				int prev=(i==0?m-1:i-1);
  79.  
  80. 				Pair curr1=al[i].get(x),curr2=al[prev].get(j);
  81.  
  82. 				if(check(i,al[i].get(x),curr2,n))
  83. 				{
  84. 					ret=(ret+solve(i+1,x,k,m,n))%mod;
  85. 				}
  86. 			}
  87.  
  88. 			dp[i][j][k]=ret;return ret;
  89. 		}
  90. 	}
  91.  
  92. 	@SuppressWarnings("unchecked")
  93. 	public static int count(int n,int[] roots,int[] a,int[] b,int[] c)
  94. 	{
  95. 		int m=roots.length;al=new ArrayList[m];tree=new ArrayList[m][n];
  96.  
  97. 		for(int i=0;i<m;i++)
  98. 		{
  99. 			al[i]=new ArrayList<Pair>();
  100. 		}
  101.  
  102.  
  103. 		for(int i=0;i<m;i++)
  104. 		{
  105. 			for(int j=0;j<n;j++)
  106. 			{
  107. 				tree[i][j]=new ArrayList<Integer>();
  108. 			}
  109. 		}
  110.  
  111.  
  112. 		for(int i=0;i<m;i++)
  113. 		{
  114. 			long[] x=new long[n-1];x[0]=c[i];
  115.  
  116. 			for(int j=1;j<=n-2;j++)
  117. 			{
  118. 				long curr=(a[i]*x[j-1]+b[i])%mod;
  119. 			}
  120.  
  121. 			for(int j=0;j<=n-2;j++)
  122. 			{
  123. 				long curr=roots[i]+j+1;curr%=n;int u=(int)curr;
  124.  
  125. 				curr=x[j]%(j+1);curr=(curr+roots[i])%n;int v=(int) curr;
  126.  
  127. 				al[i].add(new Pair(u,v));
  128.  
  129. 				tree[i][u].add(v);tree[i][v].add(u);
  130. 			}
  131. 		}
  132.  
  133. 		dp=new long[55][55][55];
  134.  
  135. 		for(int i=0;i<maxn;i++)
  136. 		{
  137. 			for(int j=0;j<maxn;j++)
  138. 			{
  139. 				for(int k=0;k<maxn;k++)
  140. 				{
  141. 					dp[i][j][k]=-1;
  142. 				}
  143. 			}
  144. 		}
  145.  
  146. 		long ret=0;
  147.  
  148. 		for(int i=0;i<=n-2;i++)
  149. 		{
  150. 			ret=(ret+solve(0,i,i,m,n))%mod;
  151. 		}
  152.  
  153. 		return (int)ret;
  154.  
  155. 	}
  156.  
  157. 	public static void main(String args[]) throws Exception
  158. 	{
  159. 		//out.println(count(3,new int[]{0, 2},new int[]{1, 2},new int[]{1, 0},new int[]{3, 5}));
  160.  
  161. 		out.close();
  162. 	}
  163. }
  164. class Pair
  165. {
  166. 	int u,v;
  167. 	public Pair(int u,int v)
  168. 	{
  169. 		this.u=u;this.v=v;
  170. 	}
  171. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:3: error: class TreeMovingDiv2 is public, should be declared in a file named TreeMovingDiv2.java
public class TreeMovingDiv2
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/7FBtH5
language:
Java (HotSpot 12)
created:
7 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!