fork download
copy 
  1. import java.io.BufferedWriter;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.OutputStream;
  5. import java.io.OutputStreamWriter;
  6. import java.io.PrintWriter;
  7. import java.io.Writer;
  8. import java.util.InputMismatchException;
  9.  
  10.  
  11.  class Solution1 {
  12.  
  13. 	/**
  14. 	 * @param args
  15. 	 */
  16. 	static int n;
  17. 	static int  m;
  18.     static int t;
  19. static int arr[];
  20. static long sum[][];
  21. static long b[];
  22. 	public static void main(String[] args) {
  23. 		// TODO Auto-generated method stub
  24. 		InputReader in=new InputReader(System.in);
  25. 		OutputWriter out=new OutputWriter(System.out);
  26.         t = in.readInt();
  27.         while(t>0){
  28. 		n=in.readInt();
  29. 		m=in.readInt();
  30. 		arr=new int[n];
  31. 		sum=new long [3][3];
  32. 		b=new long[3];
  33.  
  34. 		for(int i=0;i<n;i++)arr[i]=in.readInt()-1;
  35.  
  36. 		long last1[][]=new long[3][3];
  37.  
  38.  
  39.  
  40. 		for(int i=0;i<n;i++){
  41. 			long pow1[][]=pow(arr[i]);
  42. 			long pow2[][]=pow(arr[i]+1 );
  43. 			long temp1[][]=mul(pow2, last1);
  44.  
  45. 			last1=add(pow1,temp1);
  46.  
  47.  
  48.  
  49.  
  50. 			sum=add(sum,last1);
  51. 		}
  52.  
  53. 		out.printLine((sum[0][0]+sum[0][1]+sum[0][2])%m);
  54.  
  55. 		out.close();
  56.          t--;   
  57.         }
  58.  
  59.  
  60. 	}
  61. 	static long []mul2(long mm[][]){
  62. 		long bb[]=new long[3];
  63. 		bb[0]=mm[0][0]*b[0]+mm[0][1]*b[1]+mm[0][2]*b[2];
  64. 		bb[1]=mm[1][0]*b[0]+mm[1][1]*b[1]+mm[1][2]*b[2];
  65. 		bb[2]=mm[2][0]*b[0]+mm[2][1]*b[1]+mm[2][2]*b[2];
  66. 		bb[0]=bb[0]%m;
  67. 		bb[1]=bb[1]%m;
  68. 		bb[1]=bb[1]%m;
  69. 		return bb;
  70. 	}
  71.  
  72. 	static long[][] pow(int n){
  73. 		long ans [][]=new long[3][3];
  74. 		ans[0][0]=1;
  75. 		ans[0][1]=1;
  76. 		ans[0][2]=1;
  77. 		ans[1][0]=1;
  78. 		ans[1][1]=0;
  79. 		ans[1][2]=0;
  80. 		ans[2][0]=0;
  81. 		ans[2][1]=0;
  82. 		ans[2][2]=1;
  83. 		if(n==0){
  84.  
  85. 			long ans1[][]=new long[3][3];
  86. 			ans1[0][0]=1;
  87. 			ans1[1][1]=1;
  88. 			ans1[2][2]=1;
  89. 			return ans1;
  90. 		}
  91.  
  92. 		else{
  93. 			long ans1[][];
  94. 			ans1=pow(n/2);
  95. 			ans1=mul(ans1, ans1);
  96. 			if(n%2==0){
  97.  
  98. 			}
  99. 			else{
  100. 				ans1=mul(ans1,ans );
  101. 			}
  102. 			return ans1;
  103. 		}
  104.  
  105. 	}
  106.  
  107.  
  108.  
  109. 	static long [][]add(long m1[][],long [][] m2){
  110. 		long ans [][]=new long[3][3];
  111. 		for(int i=0;i<3;i++){
  112. 			for(int j=0;j<3;j++){
  113. 				ans[i][j]=m1[i][j]+m2[i][j];
  114. 				ans[i][j]=ans[i][j]%m;
  115. 			}
  116. 		}
  117. 		return ans;
  118. 	}
  119. 	static long [][] mul(long m1[][],long m2[][]){
  120. 		long ans [][]=new long[3][3];
  121. 		for(int i=0;i<3;i++){
  122. 			for(int j=0;j<3;j++){
  123. 				for(int k=0;k<3;k++){
  124. 				ans[i][j]=ans[i][j]+m1[i][k]*m2[k][j];
  125. 				ans[i][j]=ans[i][j]%m;
  126. 				}
  127. 			}
  128. 		}
  129. 		return ans;
  130. 	}
  131.  
  132.  
  133. }
  134. class InputReader {
  135.  
  136. 	private InputStream stream;
  137. 	private byte[] buf = new byte[1024];
  138. 	private int curChar;
  139. 	private int numChars;
  140. 	private SpaceCharFilter filter;
  141.  
  142. 	public InputReader(InputStream stream) {
  143. 		this.stream = stream;
  144. 	}
  145.  
  146. 	public int read() {
  147. 		if (numChars == -1)
  148. 			throw new InputMismatchException();
  149. 		if (curChar >= numChars) {
  150. 			curChar = 0;
  151. 			try {
  152. 				numChars = stream.read(buf);
  153. 			} catch (IOException e) {
  154. 				throw new InputMismatchException();
  155. 			}
  156. 			if (numChars <= 0)
  157. 				return -1;
  158. 		}
  159. 		return buf[curChar++];
  160. 	}
  161.  
  162. 	public int readInt() {
  163. 		int c = read();
  164. 		while (isSpaceChar(c))
  165. 			c = read();
  166. 		int sgn = 1;
  167. 		if (c == '-') {
  168. 			sgn = -1;
  169. 			c = read();
  170. 		}
  171. 		int res = 0;
  172. 		do {
  173. 			if (c < '0' || c > '9')
  174. 				throw new InputMismatchException();
  175. 			res *= 10;
  176. 			res += c - '0';
  177. 			c = read();
  178. 		} while (!isSpaceChar(c));
  179. 		return res * sgn;
  180. 	}
  181.  
  182. 	public String readString() {
  183. 		int c = read();
  184. 		while (isSpaceChar(c))
  185. 			c = read();
  186. 		StringBuilder res = new StringBuilder();
  187. 		do {
  188. 			res.appendCodePoint(c);
  189. 			c = read();
  190. 		} while (!isSpaceChar(c));
  191. 		return res.toString();
  192. 	}
  193.  
  194. 	public boolean isSpaceChar(int c) {
  195. 		if (filter != null)
  196. 			return filter.isSpaceChar(c);
  197. 		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  198. 	}
  199.  
  200. 	public String next() {
  201. 		return readString();
  202. 	}
  203.  
  204. 	public interface SpaceCharFilter {
  205. 		public boolean isSpaceChar(int ch);
  206. 	}
  207. }
  208.  
  209. class OutputWriter {
  210. 	private final PrintWriter writer;
  211.  
  212. 	public OutputWriter(OutputStream outputStream) {
  213. 		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  214. 	}
  215.  
  216. 	public OutputWriter(Writer writer) {
  217. 		this.writer = new PrintWriter(writer);
  218. 	}
  219.  
  220. 	public void print(Object...objects) {
  221. 		for (int i = 0; i < objects.length; i++) {
  222. 			if (i != 0)
  223. 				writer.print(' ');
  224. 			writer.print(objects[i]);
  225. 		}
  226. 	}
  227.  
  228. 	public void printLine(Object...objects) {
  229. 		print(objects);
  230. 		writer.println();
  231. 	}
  232.  
  233. 	public void close() {
  234. 		writer.close();
  235. 	}
  236.  
  237. 	public void flush() {
  238. 		writer.flush();
  239. 	}
  240.  
  241. 	}
  242.  
  243. class IOUtils {
  244.  
  245. 	public static int[] readIntArray(InputReader in, int size) {
  246. 		int[] array = new int[size];
  247. 		for (int i = 0; i < size; i++)
  248. 			array[i] = in.readInt();
  249. 		return array;
  250. 	}
  251.  
  252. 	}
Runtime error #stdin #stdout #stderr 0.06s 320576KB
comments ()
stdin
copy 
1
3 60
1 2 3
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.InputMismatchException
	at InputReader.read(Main.java:148)
	at InputReader.readInt(Main.java:163)
	at Solution1.main(Main.java:34)
https://ideone.com/VIbx9J
language:
Java (HotSpot 12)
created:
8 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!