fork download
copy 
  1.  
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. public class DrBTreeII {
  6.  
  7. 	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  8. 	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
  9. 	static StringTokenizer st = new StringTokenizer("");
  10.  
  11. 	public static String next() {
  12. 		try	{
  13. 		while (!st.hasMoreTokens()) {
  14. 			String s = br.readLine();
  15. 			if (s == null)
  16. 				return null;
  17. 			st = new StringTokenizer(s);
  18. 		}
  19. 		return st.nextToken();
  20. 		}	catch(Exception e)	{
  21. 			return	null;
  22. 		}
  23. 	}
  24. 	public static void main(String[] asda) throws Exception {
  25. 		mem = new int [1005][1005];
  26. 		for (int [] v : mem)	Arrays.fill(v, -1);
  27.  
  28. 		int CASES = Integer.parseInt( next() );
  29. 		while	(CASES-- > 0)	{
  30. 			int L = Integer.parseInt( next() );
  31. 			int K = Integer.parseInt( next() );
  32.  
  33. 			int ans = solve(L, K);
  34. 			out.println( ans );
  35. 		}
  36.         //
  37.         out.flush();
  38.         System.exit(0);
  39.     }
  40.  
  41.     static final long MOD = 1000000000 + 7, CHARS = 10;
  42.     static int [][] mem;
  43.     static int solve(int len, int mirrors)	{
  44.     	if (len == 0 && mirrors == 0) {
  45.     		return	1;
  46.     	}
  47.     	if (len < 0 || mirrors < 0) {
  48.     		return	0;
  49.     	}
  50.  
  51.     	if (mem[len][mirrors] != -1) {
  52.     		return mem[len][mirrors];
  53.     	}
  54.  
  55.     	long ans = 0;
  56.     	if (len % 2 == 1) {
  57.     		// place middle
  58.     		ans = CHARS * solve(len - 1, mirrors - 1);
  59.     		ans %= MOD;
  60.     	}	else	{
  61.     		// place not mirror
  62.     		ans = CHARS * (CHARS - 1) * solve(len - 2, mirrors);
  63.     		ans %= MOD;
  64.  
  65.     		ans += CHARS * solve(len - 2, mirrors - 1);
  66.     		ans %= MOD;
  67.     	}
  68.     //	out.printf("solve(%d, %d) = %d\n", len, mirrors, ans);
  69.     	return	mem[len][mirrors] = (int)ans;
  70.     }
  71.  
  72. }
  73.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:5: error: class DrBTreeII is public, should be declared in a file named DrBTreeII.java
public class DrBTreeII {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/lacNAc
language:
Java (HotSpot 12)
created:
9 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!