APCS 2024 Jan Java Solution

前言

因為大學了，就不去占名額(想當初搶得要死的)，我就沒去報名了。

P1 遊戲選角

這題可以開兩個陣列或一個 pair 陣列記起來，第一次記住整題最大值，再掃過第二次時候避開最大值的地方(因為題目保證相異)，記住第二大的是哪一個就可以了。 時間/空間複雜度

$O(N)$，另外用排序也可以，複雜度會爛一點但這題數據很小所以沒啥差別，只是也沒比較好寫。

附上精選 code: (管 Main() 就好，下面是模板)

import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main{
	public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    public static long ret,cnt;
	public static int reti,rd,n,m,ans;
	public static String[] in;
	public static String in1="";
	public static boolean neg,b1,b2,b3;
	public static void main(String[] args) throws Exception{
		final int n=readint(); // input
		int mux=0,mux2=0,id=0; //mux = max, mux2 = 2nd max
		int[] a=new int[n]; 
		int[] b=new int[n]; 
		for(int i=0;i<n;i++) {
			a[i]=readint();
			b[i]=readint();
			mux=Math.max(mux, a[i]*a[i]+b[i]*b[i]);
		}
		for(int i=0;i<n;i++) {
			int p=a[i]*a[i]+b[i]*b[i];
			if(p!=mux&&p>mux2) {
				mux2=p;
				id=i;
			}
		}
		outn(a[id]+" "+b[id]); //output
 	}
	
	
/*

 */
	//fast io
	public static int readint() throws Exception{
		reti=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
		}
		while(rd>47&&rd<58) {
			reti*=10;
			reti+=(rd&15);
			rd=br.read();
		}
		if(neg)reti*=-1;
		return reti;
	}
	public static long readlong() throws Exception{
		ret=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
		}
		while(rd>47&&rd<58) {
			ret*=10;
			ret+=(rd&15);
			rd=br.read();
		}
		if(neg)ret*=-1;
		return ret;
	}
	//fast typing
	public static int pint(String in) {
		return Integer.parseInt(in);
	}
	public static long plong(String in) {
		return Long.parseLong(in);
	}
	public static void outn() {
		System.out.println();
	}
	public static void outn(char in) {
		System.out.println(in);
	}
	public static void outn(long in) {
		System.out.println(in);
	}
	public static void outn(double in) {
		System.out.println(in);
	}
	public static void outn(boolean in) {
		System.out.println(in);
	}
	public static void outn(String in) {
		System.out.println(in);
	}
	public static void out(char in) {
		System.out.print(in);
	}
	public static void out(long in) {
		System.out.print(in);
	}
	public static void out(double in) {
		System.out.print(in);
	}
	public static void out(boolean in) {
		System.out.print(in);
	}
	public static void out(String in) {
		System.out.print(in);
	}
	public static void fl() {
		System.out.flush();
	}
	public static String[] res() throws IOException{
		return br.readLine().split(" ");
	}
	public static String re() throws IOException{
		return br.readLine().split(" ")[0];
	}
}

P2 蜜蜂觀察

六邊形的很難寫，但我們把它變成熟悉的形狀就好了。

這樣應該會比較好理解，而我們依照上面的定義可以用

$(x,y)$的坐標系表示，把這題的向量

$\overrightarrow{v_0}=(1,0),\overrightarrow{v_1}=(0,1),\overrightarrow{v_2}=(1,1)$ ，而對於

$i\ge 3$ 我們有

$\overrightarrow{v_i}=-\overrightarrow{v_{i-3}}$，也就是乘以

$-1$ 的 scalar 。再判斷邊界就可以了，時間/空間複雜度

$O(NM+K)$。

最後要判斷的話，因為字元沒很多種，要算他的貢獻的話直接開個 boolean 陣列記，最後再整個跑一次看哪些有走過就在答案

$+1$ 就可以了。

附上精選 code: (以下的

$x$ 方向為了方便寫跟上面的方向是相反的)

import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main{
	public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	public static long ret,cnt;
	public static int reti,rd,n,m,ans;
	public static String[] in;
	public static String in1="";
	public static boolean neg,b1,b2,b3;
	public static void main(String[] args) throws Exception{
		char[][] mp=new char[105][105];
		in=res();
		final int n=pint(in[0]);
		final int m=pint(in[1]);
		final int k=pint(in[2]);
		for(int i=1;i<=n;i++) {
			in=res();
			for(int j=1;j<=m;j++) {
				mp[i][j]=in[0].charAt(j-1); //honeycomb
			}
		}
		boolean[] b=new boolean[100];
		int x=n,y=1,nx=n,ny=1; //nx, ny = new_x, new_y
		String S="";
		in=res();
		for(int i=0;i<k;i++) {
			int d=pint(in[i]); //get movement 
			int c=1;
			if(d>2) { // scalar *= -1
				d-=3;
				c=-1;
			}
			if(d==0) {
				nx=x-c;
				ny=y;
			}
			if(d==1) {
				nx=x;
				ny=y+c;
			}
			if(d==2) {
				nx=x+c;
				ny=y+c;
			}
			if(nx<=n&&ny<=m&&nx*ny>0) {
				x=nx; //not out of bound
				y=ny;
			}
			S+=mp[x][y];
			b[mp[x][y]-'A']=true; //boolean
		}
		int ans=0;
		for(boolean i:b) {
			if(i) ans++;
		}
		outn(S);
		outn(ans);
 	}
	
	
/*

 */
	//fast io
	public static int readint() throws Exception{
		reti=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
		}
		while(rd>47&&rd<58) {
			reti*=10;
			reti+=(rd&15);
			rd=br.read();
		}
		if(neg)reti*=-1;
		return reti;
	}
	public static long readlong() throws Exception{
		ret=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
		}
		while(rd>47&&rd<58) {
			ret*=10;
			ret+=(rd&15);
			rd=br.read();
		}
		if(neg)ret*=-1;
		return ret;
	}
	//fast typing
	public static int pint(String in) {
		return Integer.parseInt(in);
	}
	public static long plong(String in) {
		return Long.parseLong(in);
	}
	public static void outn() {
		System.out.println();
	}
	public static void outn(char in) {
		System.out.println(in);
	}
	public static void outn(long in) {
		System.out.println(in);
	}
	public static void outn(double in) {
		System.out.println(in);
	}
	public static void outn(boolean in) {
		System.out.println(in);
	}
	public static void outn(String in) {
		System.out.println(in);
	}
	public static void out(char in) {
		System.out.print(in);
	}
	public static void out(long in) {
		System.out.print(in);
	}
	public static void out(double in) {
		System.out.print(in);
	}
	public static void out(boolean in) {
		System.out.print(in);
	}
	public static void out(String in) {
		System.out.print(in);
	}
	public static void fl() {
		System.out.flush();
	}
	public static String[] res() throws IOException{
		return br.readLine().split(" ");
	}
	public static String re() throws IOException{
		return br.readLine().split(" ")[0];
	}
}

P3 邏輯電路

這題就是一個

$\text{bfs}$ 裸題，照題目的實作就可以了，定義一個 Queue 叫做

$Q$，一開始先把起點都丟進去，之後拜訪到中間節點(邏輯閘)，因為有一些節點的入

$deg=2$，一邊到了之後另一邊可能還沒走到，所以對於

$deg=2$ 要判斷兩邊都走過後才可以把它丟進

$Q$ 裡面，最深深度可以開一個陣列，定義

$dist(i)$ 走到

$i$ 時的最遠距離 (我們定義

$dist(x)=0,1\le x\le p$)，那我們算出所有的

$dist(i)$ 後，把

$dist(x)(p+q+1\le x\le p+q+r)$ 取最大值就會是題目所求，要注意題目沒保證全部的邏輯閘都接到終點，你取

$1\le x\le p+q+r$ 會是錯的(有可能中間走到死路，但距離更長)，這題的測試資料便是如此，時間複雜度

$O(p+q+r+m)$。
code: (最下面那堆是模板)

import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main{
	public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	public static long ret,cnt;
	public static int reti,rd,n,m,ans;
	public static String[] in;
	public static String in1="";
	public static boolean neg,b1,b2,b3;
	public static final int mod=998244353,mox=998244352,mod2=1_000_000_007,ma=1000015;
	public static Useful us=new Useful(mod);
	public static ArrayList<ArrayList<Integer>> E=new ArrayList<>();
	public static void main(String[] args) throws Exception{
		int MAXN=60000;
		final int p=readint();
		final int q=readint();
		final int r=readint();
		final int m=readint();
		int[] type=new int[MAXN];
		int[] value=new int[MAXN];
		int[] cnt=new int[MAXN];
		int[] deg=new int[MAXN];
		Queue<Integer> Q=new LinkedList<>();
		for(int i=1;i<=p;i++) {
			value[i]=readint();
			Q.offer(i); // init queue
		}
		for(int i=p+1;i<=p+q;i++) {
			type[i]=readint();
		}
		us.al(E,p+q+r+5); //init arraylist
		for(int i=0;i<m;i++) {
			E.get(readint()).add(readint()); // add direct edge
		}
		int o, ans=0;
		while(!Q.isEmpty()) {
			o=Q.poll();
			for(int i:E.get(o)) {
				if(i<=p+q) {
					if(type[i]==4) { // not
						value[i]=value[o]^1;
						Q.offer(i);
					}
					else if(deg[i]==0) { //first, no queuing.
						deg[i]=1;
						value[i]=value[o];
					}
					else {
						if(type[i]==1) value[i]&=value[o];
						if(type[i]==2) value[i]|=value[o];
						if(type[i]==3) value[i]^=value[o];
						Q.offer(i);
					}
				}
				else {
					value[i]=value[o];
				}
				cnt[i]=Math.max(cnt[o]+1, cnt[i]); //cal dist
			}
		}
		for(int i=p+q+1;i<=p+q+r;i++) {
			ans=Math.max(cnt[i]-1, ans); //dist
		}
		bw.write(ans+"\n");
		for(int i=p+q+1;i<=p+q+r;i++) {
			bw.write(value[i]+" ");
		}
		bw.flush();
 	}

	//fast io
	public static int readint() throws Exception{
		reti=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
		}
		while(rd>47&&rd<58) {
			reti*=10;
			reti+=(rd&15);
			rd=br.read();
		}
		if(neg)reti*=-1;
		return reti;
	}
	public static long readlong() throws Exception{
		ret=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
		}
		while(rd>47&&rd<58) {
			ret*=10;
			ret+=(rd&15);
			rd=br.read();
		}
		if(neg)ret*=-1;
		return ret;
	}
	//fast typing
	public static int pint(String in) {
		return Integer.parseInt(in);
	}
	public static long plong(String in) {
		return Long.parseLong(in);
	}
	public static void outn() {
		System.out.println();
	}
	public static void outn(char in) {
		System.out.println(in);
	}
	public static void outn(long in) {
		System.out.println(in);
	}
	public static void outn(double in) {
		System.out.println(in);
	}
	public static void outn(boolean in) {
		System.out.println(in);
	}
	public static void outn(String in) {
		System.out.println(in);
	}
	public static void out(char in) {
		System.out.print(in);
	}
	public static void out(long in) {
		System.out.print(in);
	}
	public static void out(double in) {
		System.out.print(in);
	}
	public static void out(boolean in) {
		System.out.print(in);
	}
	public static void out(String in) {
		System.out.print(in);
	}
	public static void fl() {
		System.out.flush();
	}
	public static String[] res() throws IOException{
		return br.readLine().split(" ");
	}
	public static String re() throws IOException{
		return br.readLine().split(" ")[0];
	}
}

class Useful{
	long mod;
	Useful(long m){mod=m;}
	void al(ArrayList<ArrayList<Integer>> a,int n){for(int i=0;i<n;i++) {a.add(new ArrayList<Integer>());}}
	void arr(int[] a,int init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
	void arr(long[] a,long init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
	void arr(int[][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
	void arr(long[][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
	void arr(int[][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
	void arr(long[][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
	void arr(int[][][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
	void arr(long[][][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
	long fastn(long x,long pw) {
		if(pw==1)return x;
		long h=fastn(x,pw>>1);
		if((pw&1)==0) {
			return h*h;
		}
		return h*h*x;
	}
	long fast(long x,long pw) {
		if(x==0)return 1;
		if(pw<=0)return 1;
		if(pw==1)return x;
		long h=fast(x,pw>>1);
		if((pw&1)==0) {
			return h*h%mod;
		}
		return h*h%mod*x%mod;
	}
	long fast(long x,long pw,long mod) {
		if(pw<=0)return 1;
		if(pw==1)return x;
		long h=fast(x,pw>>1,mod);
		if((pw&1)==0) {
			return h*h%mod;
		}
		return h*h%mod*x%mod;
	}
	long[][] mul(long[][] a,long[][] b){
		long[][] c=new long[a.length][b[0].length];
		for(int i=0;i<a.length;i++) {
			for(int j=0;j<b[0].length;j++) {
				for(int k=0;k<a[0].length;k++) {
					c[i][j]+=a[i][k]*b[k][j];
					c[i][j]%=mod;
				}
			}
		}
		return c;
	}
	long[][] mul(long[][] a,long[][] b,long mod){
		long[][] c=new long[a.length][b[0].length];
		for(int i=0;i<a.length;i++) {
			for(int j=0;j<b[0].length;j++) {
				for(int k=0;k<a[0].length;k++) {
					c[i][j]+=a[i][k]*b[k][j];
					c[i][j]%=mod;
				}
			}
		}
		return c;
	}
	long[][] fast(long[][] x,long pw){
		if(pw==1)return x;
		long[][] h=fast(x,pw>>1);
		if((pw&1)==0) {
			return mul(h,h);
		}
		else {
			return mul(mul(h,h),x);
		}
	}
	long[][] fast(long[][] x,long pw,long mod){
		if(pw==1)return x;
		long[][] h=fast(x,pw>>1,mod);
		if((pw&1)==0) {
			return mul(h,h,mod);
		}
		else {
			return mul(mul(h,h,mod),x,mod);
		}
	}
	int gcd(int a,int b) {
		if(a==0)return b;
		if(b==0)return a;
		return gcd(b,a%b);
	}
	long gcd(long a,long b) {
		if(a==0)return b;
		if(b==0)return a;
		return gcd(b,a%b);
	}
	long lcm(long a, long b){
	    return a*(b/gcd(a,b));
	}
	double log2(long x) {
		return (Math.log(x)/Math.log(2));
	}
	double logx(long x,long y) {
		return (Math.log(y)/Math.log(x));
	}
}

P4 合併成本

定義

$dp(L,R)$ 代表合併區間

$[L,R]$ 成一個的答案，要合併兩個數，如以下範例的紅藍兩個要合併，因為他是在一條線上的，那其實我們可以把它想回拆解前的狀態。

會發現紅、藍、紅

$\cup$ 藍都是連續的，因為這個性質，那勢必答案可以表示成

$dp(L_{\mathrm{紅}},R_{\mathrm{紅}})+dp(L_{\mathrm{藍}},R_{\mathrm{藍}})+\mathrm{這}\mathrm{兩}\mathrm{塊}\mathrm{合}\mathrm{併}\mathrm{的}cost$。

具體的做法
以下的程式是用 dp-memorization 的方式，先呼叫

$dp(1,N)$，之後往下窮舉各個切法，切成

$[L,mid],[mid+1,R]$ 兩塊後繼續算，記得算過的要存入

$dp$ 陣列就不用重複算，時間複雜度

$O(N^3)$。另外維護前綴和可以做到

$O(1)$ 查詢兩塊各自的 weight，但其實除了前綴和也有別的做法可以做到整體複雜度相同的維護，只是比較麻煩。

Code:

import java.util.*;
import java.time.*;
import java.io.*;
import java.math.*;
public class Main{
	public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	public static long ret,cnt;
	public static int reti,rd,n,m,ans;
	public static String[] in;
	public static String in1="";
	public static boolean neg,b1,b2,b3;
	public static final int mod=998244353,mox=998244352,mod2=1_000_000_007,ma=1000015;
	public static Useful us=new Useful(mod);
	public static long[] Al=new long[105];
	public static long[][] dp=new long[105][105];
	public static long[] p=new long[105];
	public static ArrayList<ArrayList<Integer>> E=new ArrayList<>();
	public static void main(String[] args) throws Exception{
		final int n=readint();
		for(int i=1;i<=n;i++) {
			Al[i]=readint();
			p[i]=Al[i]+p[i-1]; //prefix sum
		}
		us.arr(dp, -1); // init dp with -1
		outn(DP(1,n)); //calculate dp [1,N]
 	}
	
	public static long DP(int l,int r) { //top down
		if(dp[l][r]!=-1)return dp[l][r]; //if calculated, return
		if(l==r)return 0; //base case
		long ans=(1L<<60);
		for(int i=l;i<r;i++) { // iterate all ways to divide l,r into 2 pieces. 
			ans=Math.min(DP(l,i)+DP(i+1,r)+Math.abs(p[r]-2*p[i]+p[l-1]), ans);
		}
		dp[l][r]=ans; //dp-memoization 
		return ans;
	}

	//fast io
	public static int readint() throws Exception{
		reti=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
		}
		while(rd>47&&rd<58) {
			reti*=10;
			reti+=(rd&15);
			rd=br.read();
		}
		if(neg)reti*=-1;
		return reti;
	}
	public static long readlong() throws Exception{
		ret=0;
		neg=false;
		while(rd<48||rd>57) {
			rd=br.read();
			if(rd=='-') {
				neg=true;
			}
		}
		while(rd>47&&rd<58) {
			ret*=10;
			ret+=(rd&15);
			rd=br.read();
		}
		if(neg)ret*=-1;
		return ret;
	}
	//fast typing
	public static int pint(String in) {
		return Integer.parseInt(in);
	}
	public static long plong(String in) {
		return Long.parseLong(in);
	}
	public static void outn() {
		System.out.println();
	}
	public static void outn(char in) {
		System.out.println(in);
	}
	public static void outn(long in) {
		System.out.println(in);
	}
	public static void outn(double in) {
		System.out.println(in);
	}
	public static void outn(boolean in) {
		System.out.println(in);
	}
	public static void outn(String in) {
		System.out.println(in);
	}
	public static void out(char in) {
		System.out.print(in);
	}
	public static void out(long in) {
		System.out.print(in);
	}
	public static void out(double in) {
		System.out.print(in);
	}
	public static void out(boolean in) {
		System.out.print(in);
	}
	public static void out(String in) {
		System.out.print(in);
	}
	public static void fl() {
		System.out.flush();
	}
	public static String[] res() throws IOException{
		return br.readLine().split(" ");
	}
	public static String re() throws IOException{
		return br.readLine().split(" ")[0];
	}
}

class Useful{
	long mod;
	Useful(long m){mod=m;}
	void al(ArrayList<ArrayList<Integer>> a,int n){for(int i=0;i<n;i++) {a.add(new ArrayList<Integer>());}}
	void arr(int[] a,int init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
	void arr(long[] a,long init) {for(int i=0;i<a.length;i++) {a[i]=init;}}
	void arr(int[][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
	void arr(long[][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {a[i][j]=init;}}}
	void arr(int[][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
	void arr(long[][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {a[i][j][k]=init;}}}}
	void arr(int[][][][] a,int init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
	void arr(long[][][][] a,long init) {for(int i=0;i<a.length;i++) {for(int j=0;j<a[i].length;j++) {for(int k=0;k<a[i][j].length;k++) {Arrays.fill(a[i][j][k],init);}}}}
	long fastn(long x,long pw) {
		if(pw==1)return x;
		long h=fastn(x,pw>>1);
		if((pw&1)==0) {
			return h*h;
		}
		return h*h*x;
	}
	long fast(long x,long pw) {
		if(x==0)return 1;
		if(pw<=0)return 1;
		if(pw==1)return x;
		long h=fast(x,pw>>1);
		if((pw&1)==0) {
			return h*h%mod;
		}
		return h*h%mod*x%mod;
	}
	long fast(long x,long pw,long mod) {
		if(pw<=0)return 1;
		if(pw==1)return x;
		long h=fast(x,pw>>1,mod);
		if((pw&1)==0) {
			return h*h%mod;
		}
		return h*h%mod*x%mod;
	}
	long[][] mul(long[][] a,long[][] b){
		long[][] c=new long[a.length][b[0].length];
		for(int i=0;i<a.length;i++) {
			for(int j=0;j<b[0].length;j++) {
				for(int k=0;k<a[0].length;k++) {
					c[i][j]+=a[i][k]*b[k][j];
					c[i][j]%=mod;
				}
			}
		}
		return c;
	}
	long[][] mul(long[][] a,long[][] b,long mod){
		long[][] c=new long[a.length][b[0].length];
		for(int i=0;i<a.length;i++) {
			for(int j=0;j<b[0].length;j++) {
				for(int k=0;k<a[0].length;k++) {
					c[i][j]+=a[i][k]*b[k][j];
					c[i][j]%=mod;
				}
			}
		}
		return c;
	}
	long[][] fast(long[][] x,long pw){
		if(pw==1)return x;
		long[][] h=fast(x,pw>>1);
		if((pw&1)==0) {
			return mul(h,h);
		}
		else {
			return mul(mul(h,h),x);
		}
	}
	long[][] fast(long[][] x,long pw,long mod){
		if(pw==1)return x;
		long[][] h=fast(x,pw>>1,mod);
		if((pw&1)==0) {
			return mul(h,h,mod);
		}
		else {
			return mul(mul(h,h,mod),x,mod);
		}
	}
	int gcd(int a,int b) {
		if(a==0)return b;
		if(b==0)return a;
		return gcd(b,a%b);
	}
	long gcd(long a,long b) {
		if(a==0)return b;
		if(b==0)return a;
		return gcd(b,a%b);
	}
	long lcm(long a, long b){
	    return a*(b/gcd(a,b));
	}
	double log2(long x) {
		return (Math.log(x)/Math.log(2));
	}
	double logx(long x,long y) {
		return (Math.log(y)/Math.log(x));
	}
}