fork(1) download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class TaskD
  5. {
  6. 	public static void main(String[] args)
  7. 	{
  8. 		new TaskD(System.in, System.out);
  9. 	}
  10.  
  11. 	static class Solver implements Runnable
  12. 	{
  13. 		static final long MOD = (long) 1e9 + 7;
  14. 		int n, m;
  15. 		int[] a, b;
  16. 		long[] unknown;
  17. 		InputReader in;
  18. 		PrintWriter out;
  19.  
  20. 		void solve() throws IOException
  21. 		{
  22. 			n = in.nextInt();
  23. 			m = in.nextInt();
  24. 			a = in.nextIntArray(n);
  25. 			b = in.nextIntArray(n);
  26. 			unknown = new long[n];
  27.  
  28. 			for (int i = n - 1; i >= 0; i--)
  29. 			{
  30. 				if (i < n - 1)
  31. 					unknown[i] = unknown[i + 1];
  32.  
  33. 				if (a[i] == 0)
  34. 					unknown[i]++;
  35.  
  36. 				if (b[i] == 0)
  37. 					unknown[i]++;
  38. 			}
  39.  
  40. 			long p = 0;
  41. 			long q = CMath.modPower(m, unknown[0], MOD);
  42. 			int bothZero = 0;
  43.  
  44. 			for (int i = 0; i < n; i++)
  45. 			{
  46. //				System.out.println("i : " + i + ", a[i] : " + a[i] + ", b[i] : " + b[i]);
  47.  
  48. 				if (a[i] == 1/* && b[i] == 0*/)
  49. 				{
  50. 					p = 0;
  51.  
  52. 					break;
  53. 				}
  54. 				else if (a[i] != 0 && b[i] != 0 && a[i] <= b[i])
  55. 					break;
  56. 				else if (a[i] == 0 && b[i] == 0)
  57. 				{
  58. 					long x = CMath.mod((m - 1) * (m - 2) / 2, MOD);
  59. 					long add = CMath.mod(x * (i < n - 1 ? CMath.modPower(m, unknown[i + 1], MOD) : 1), MOD);
  60.  
  61. 					add = CMath.mod(add * CMath.modPower(m, bothZero, MOD), MOD);
  62. 					p = CMath.mod(p + add, MOD);
  63. 					bothZero++;
  64. 				}
  65. 				else if (a[i] == 0)
  66. 				{
  67. 					long add = CMath.mod((m - b[i]) * (i < n - 1 ? CMath.modPower(m, unknown[i + 1], MOD) : 1), MOD);
  68.  
  69. 					add = CMath.mod(add * CMath.modPower(m, bothZero, MOD), MOD);
  70. 					p = CMath.mod(p + add, MOD);
  71. 				}
  72. 				else if (b[i] == 0)
  73. 				{
  74. 					long add = CMath.mod((a[i] - 1) * (i < n - 1 ? CMath.modPower(m, unknown[i + 1], MOD) : 1), MOD);
  75.  
  76. 					add = CMath.mod(add * CMath.modPower(m, bothZero, MOD), MOD);
  77. 					p = CMath.mod(p + add, MOD);
  78. 				}
  79. 				else if (a[i] > b[i])
  80. 				{
  81. 					long add = (i < n - 1 ? CMath.modPower(m, unknown[i + 1], MOD) : 1);
  82.  
  83. 					add = CMath.mod(add * CMath.modPower(m, bothZero, MOD), MOD);
  84. 					p = CMath.mod(p + add, MOD);
  85. 				}
  86. //				System.out.println("\ti : " + i + ", p : " + p);
  87. 			}
  88.  
  89. 			System.out.println("p : " + p + ", q : " + q);
  90.  
  91. 			if (p == 0)
  92. 				out.println(0);
  93. 			else
  94. 			{
  95. 				long gcd = CMath.gcd(p, q);
  96.  
  97. 				p /= gcd;
  98. 				q /= gcd;
  99. 				q = CMath.moduloInverse(q, MOD);
  100. 				out.println(CMath.mod(p * q, MOD));
  101. 			}
  102. 		}
  103.  
  104. 		public Solver(InputReader in, PrintWriter out)
  105. 		{
  106. 			this.in = in;
  107. 			this.out = out;
  108. 		}
  109.  
  110. 		@Override public void run()
  111. 		{
  112. 			try
  113. 			{
  114. 				solve();
  115. 			}
  116. 			catch (IOException e)
  117. 			{
  118. 				e.printStackTrace();
  119. 			}
  120. 		}
  121.  
  122. 	}
  123.  
  124. 	static class InputReader
  125. 	{
  126. 		private InputStream stream;
  127. 		private byte[] buf = new byte[1024];
  128. 		private int curChar;
  129. 		private int numChars;
  130.  
  131. 		public int read()
  132. 		{
  133. 			if (numChars == -1)
  134. 				throw new InputMismatchException();
  135.  
  136. 			if (curChar >= numChars)
  137. 			{
  138. 				curChar = 0;
  139. 				try
  140. 				{
  141. 					numChars = stream.read(buf);
  142. 				}
  143. 				catch (IOException e)
  144. 				{
  145. 					throw new InputMismatchException();
  146. 				}
  147. 				if (numChars <= 0)
  148. 					return -1;
  149. 			}
  150.  
  151. 			return buf[curChar++];
  152. 		}
  153.  
  154. 		public int nextInt()
  155. 		{
  156. 			int c = read();
  157.  
  158. 			while (isSpaceChar(c))
  159. 				c = read();
  160.  
  161. 			int sgn = 1;
  162.  
  163. 			if (c == '-')
  164. 			{
  165. 				sgn = -1;
  166. 				c = read();
  167. 			}
  168.  
  169. 			int res = 0;
  170.  
  171. 			do
  172. 			{
  173. 				if (c < '0' || c > '9')
  174. 					throw new InputMismatchException();
  175.  
  176. 				res *= 10;
  177. 				res += c & 15;
  178.  
  179. 				c = read();
  180. 			} while (!isSpaceChar(c));
  181.  
  182. 			return res * sgn;
  183. 		}
  184.  
  185. 		public int[] nextIntArray(int arraySize)
  186. 		{
  187. 			int array[] = new int[arraySize];
  188.  
  189. 			for (int i = 0; i < arraySize; i++)
  190. 				array[i] = nextInt();
  191.  
  192. 			return array;
  193. 		}
  194.  
  195. 		public boolean isSpaceChar(int c)
  196. 		{
  197. 			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  198. 		}
  199.  
  200. 		public void close()
  201. 		{
  202. 			try
  203. 			{
  204. 				stream.close();
  205. 			}
  206. 			catch (IOException e)
  207. 			{
  208. 				e.printStackTrace();
  209. 			}
  210. 		}
  211.  
  212. 		public InputReader(InputStream stream)
  213. 		{
  214. 			this.stream = stream;
  215. 		}
  216.  
  217. 	}
  218.  
  219. 	static class CMath
  220. 	{
  221. 		static long modPower(long number, long power, long mod)
  222. 		{
  223. 			if (number == 1 || number == 0 || power == 0)
  224. 				return 1;
  225.  
  226. 			number = mod(number, mod);
  227.  
  228. 			if (power == 1)
  229. 				return number;
  230.  
  231. 			long square = mod(number * number, mod);
  232.  
  233. 			if (power % 2 == 0)
  234. 				return modPower(square, power / 2, mod);
  235. 			else
  236. 				return mod(modPower(square, power / 2, mod) * number, mod);
  237. 		}
  238.  
  239. 		static long moduloInverse(long number, long mod)
  240. 		{
  241. 			return modPower(number, mod - 2, mod);
  242. 		}
  243.  
  244. 		static long mod(long number, long mod)
  245. 		{
  246. 			return number - (number / mod) * mod;
  247. 		}
  248.  
  249. 		static long gcd(long a, long b)
  250. 		{
  251. 			if (b == 0)
  252. 				return a;
  253. 			else
  254. 				return gcd(b, a % b);
  255. 		}
  256.  
  257. 	}
  258.  
  259. 	public TaskD(InputStream inputStream, OutputStream outputStream)
  260. 	{
  261. 		InputReader in = new InputReader(inputStream);
  262. 		PrintWriter out = new PrintWriter(outputStream);
  263. 		Thread thread = new Thread(null, new Solver(in, out), "TaskD", 1 << 29);
  264.  
  265. 		try
  266. 		{
  267. 			thread.start();
  268. 			thread.join();
  269. 		}
  270. 		catch (InterruptedException e)
  271. 		{
  272. 			e.printStackTrace();
  273. 		}
  274. 		finally
  275. 		{
  276. 			in.close();
  277. 			out.flush();
  278. 			out.close();
  279. 		}
  280. 	}
  281.  
  282. }
  283.  
  284.  
Success #stdin #stdout 0.06s 27884KB
comments (?)
stdin
copy 
7 26
0 15 12 9 13 0 14
11 1 0 13 15 12 0
stdout
copy 
p : 288652, q : 456976
897929001
https://ideone.com/xqx59c
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

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!