fork download
copy 
  1. public class FoxAndSouvenir
  2. {
  3. 	static final long mod = 1000000009, primitiveRoot = 13;
  4.  
  5. 	long power(long b, long exp)
  6. 	{
  7. 		long ret = 1;
  8. 		while(exp > 0)
  9. 		{
  10. 			if(exp % 2 == 1) ret = (ret * b) % mod;
  11. 			b = (b * b) % mod;
  12. 			exp /= 2;
  13. 		}
  14. 		return ret;
  15. 	}
  16.  
  17. 	int N;
  18. 	long r, invN;
  19. 	long [] a, invA; // a[i] = r^i
  20. 	long [] b, invB; // b[i] = 1 + r^i
  21.  
  22. 	void prepare()
  23. 	{
  24. 		N = 3507; // we should have (mod-1) % N == 0, N % 2 == 1
  25. 		r = power(primitiveRoot, (mod - 1) / N);
  26. 		invN = power(N, mod - 2);
  27. 		a = new long[N]; invA = new long[N];
  28. 		b = new long[N]; invB = new long[N];
  29. 		for(int i = 0; i < N; i++)
  30. 		{
  31. 			a[i] = power(r, i);
  32. 			invA[i] = power(a[i], mod - 2);
  33. 			b[i] = (a[i] + 1) % mod;
  34. 			invB[i] = power(b[i], mod - 2);
  35. 		}
  36. 	}
  37.  
  38. 	public int[] waysToBuy(int n, int m, int[] price, int[] xMin, int[] xMax, int[] yMin, int[] yMax, int[] require)
  39. 	{
  40. 		prepare();
  41. 		int [][][] s = new int[n][m][N];
  42. 		int [][][] invS = new int[n][m][N];
  43. 		for(int i = 0; i < n; i++)
  44. 			for(int j = 0; j < m; j++)
  45. 			{
  46. 				int id = 0;
  47. 				for(int k = 0; k < N; k++)
  48. 				{
  49. 					s[i][j][k] = (int)(price[i*m+j] == 0 ? 1 : b[id]);
  50. 					invS[i][j][k] = (int)(price[i*m+j] == 0 ? 1 : invB[id]);
  51. 					id += price[i*m+j];
  52. 					if(id >= N)
  53. 						id -= N;
  54. 					if(i > 0)
  55. 					{
  56. 						s[i][j][k] = (int)(((long)s[i][j][k] * s[i-1][j][k]) % mod);
  57. 						invS[i][j][k] = (int)(((long)invS[i][j][k] * invS[i-1][j][k]) % mod);
  58. 					}
  59. 					if(j > 0)
  60. 					{
  61. 						s[i][j][k] = (int)(((long)s[i][j][k] * s[i][j-1][k]) % mod);
  62. 						invS[i][j][k] = (int)(((long)invS[i][j][k] * invS[i][j-1][k]) % mod);
  63. 					}
  64. 					if(i > 0 && j > 0)
  65. 					{
  66. 						s[i][j][k] = (int)(((long)s[i][j][k] * invS[i-1][j-1][k]) % mod);
  67. 						invS[i][j][k] = (int)(((long)invS[i][j][k] * s[i-1][j-1][k]) % mod);
  68. 					}
  69. 				}
  70. 			}
  71. 		int nQuery = xMin.length;
  72. 		int[] ret = new int[nQuery];
  73. 		for(int i = 0; i < nQuery; i++)
  74. 		{
  75. 			long v = 0;
  76. 			int id = 0;
  77. 			for(int k = 0; k < N; k++)
  78. 			{
  79. 				long t = invA[id];
  80. 				id += require[i];
  81. 				if(id >= N) id -= N;
  82. 				t = (t * s[xMax[i]][yMax[i]][k]) % mod;
  83. 				if(xMin[i] > 0)
  84. 					t = (t * invS[xMin[i]-1][yMax[i]][k]) % mod;
  85. 				if(yMin[i] > 0)
  86. 					t = (t * invS[xMax[i]][yMin[i]-1][k]) % mod;
  87. 				if(xMin[i] > 0 && yMin[i] > 0)
  88. 					t = (t * s[xMin[i]-1][yMin[i]-1][k]) % mod;
  89. 				v = (v + t) % mod;
  90. 			}
  91. 			v = (v * invN) % mod;
  92. 			ret[i] = (int) v;
  93. 		}
  94. 		return ret;
  95. 	}
  96. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: class FoxAndSouvenir is public, should be declared in a file named FoxAndSouvenir.java
public class FoxAndSouvenir
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/9JXoSL
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!