#118930 (Java21) No.426 往復漸化式

提出ソース

結果

問題	No.426 往復漸化式
ユーザー	uwi
提出日時	2016-09-23 00:48:34
言語	Java21 (openjdk 21)
結果	AC
実行時間	2,166 ms / 5,000 ms
コード長	9,161 bytes
コンパイル時間	4,597 ms
コンパイル使用メモリ	86,360 KB
実行使用メモリ	224,556 KB
最終ジャッジ日時	2024-11-17 15:38:19
合計ジャッジ時間	34,905 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	101 ms 40,804 KB
testcase_01	AC	131 ms 41,992 KB
testcase_02	AC	121 ms 41,812 KB
testcase_03	AC	258 ms 47,464 KB
testcase_04	AC	247 ms 47,236 KB
testcase_05	AC	604 ms 71,012 KB
testcase_06	AC	643 ms 66,156 KB
testcase_07	AC	1,781 ms 199,296 KB
testcase_08	AC	1,810 ms 199,396 KB
testcase_09	AC	1,957 ms 200,548 KB
testcase_10	AC	1,936 ms 201,016 KB
testcase_11	AC	1,345 ms 194,608 KB
testcase_12	AC	1,769 ms 200,908 KB
testcase_13	AC	2,029 ms 209,572 KB
testcase_14	AC	1,814 ms 200,392 KB
testcase_15	AC	1,323 ms 194,964 KB
testcase_16	AC	1,674 ms 200,696 KB
testcase_17	AC	1,784 ms 200,008 KB
testcase_18	AC	1,645 ms 200,192 KB
testcase_19	AC	1,540 ms 199,628 KB
testcase_20	AC	1,767 ms 205,912 KB
testcase_21	AC	2,166 ms 224,556 KB
testcase_22	AC	1,753 ms 205,560 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

package contest;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StringReader;
import java.util.Arrays;

public class N426 {
	static BufferedReader br;
	static PrintWriter out;
	static String INPUT = "";
	
	static int[] nia() throws Exception
	{
		String[] sp = br.readLine().split(" ");
		int[] ret = new int[sp.length];
		for(int i = 0;i < ret.length;i++){
			ret[i] = Integer.parseInt(sp[i]);
		}
		return ret;
	}
	
	// b4 = B5b5+[30]A4A3A2A1A0a0
	// b3 = B4(B5b5+[5]A4A3A2A1A0a0)+[4]A3A2A1A0a0
	// b3 = B4B5b5+(B4[5]A4+[4])A3A2A1A0a0
	// b2 = B3B4B5b5+B3(B4[5]A4+[4])A3A2A1A0a0+[3]A2A1A0a0
	// b2 = B3B4B5b5+(B3(B4[5]A4+[4])A3)+[3])A2A1A0a0
	
	// b2 = XA2A1A0a0
	// b1 = B2(XA2A1A0a0)+YA1A0a0
	// b1 = B1(B2(XA2A1A0a0)+YA1A0a0)+ZA0a0
	// B1(B2XA2+Y)A1+Z
	// B1B2*X*A2+YA1+Z
	
	static void solve() throws Exception
	{
		int n = Integer.parseInt(br.readLine());
		int[] a = nia();
		int[] b = nia();
		assert a.length == 3;
		assert b.length == 2;
		int q = Integer.parseInt(br.readLine());
		SegmentTreeMatrix sta = new SegmentTreeMatrix(n+1, 3);
		SegmentTreeMatrix stb = new SegmentTreeMatrix(n+1, 2);
		SegmentTreeNode stx = new SegmentTreeNode(n+1);
		
		int[][] V = {
			{0, 0, 0},
			{0, 0, 0}
		};
		
		for(int i = 0;i < q;i++){
			String[] sp = br.readLine().split(" ");
			if(sp[0].equals("a")){
				int ind = Integer.parseInt(sp[1]);
				int p = 2;
				for(int j = 0;j < 3;j++){
					for(int k = 0;k < 3;k++){
						int val = Integer.parseInt(sp[p]);
						sta.node[sta.H+ind][j][k] = val;
						stx.node[stx.H+n-ind].A[j][k] = val;
						p++;
					}
				}
				sta.update(ind);
				stx.update(n-ind);
			}else if(sp[0].equals("b")){
				int ind = Integer.parseInt(sp[1]);
				int p = 2;
				for(int j = 0;j < 2;j++){
					for(int k = 0;k < 2;k++){
						int val = Integer.parseInt(sp[p]);
						stb.node[stb.H+n-ind][j][k] = val;
						stx.node[stx.H+n-ind].B[j][k] = val;
						p++;
					}
				}
				stb.update(n-ind);
				stx.update(n-ind);
			}else if(sp[0].equals("ga")){
				int ind = Integer.parseInt(sp[1]);
				int[] v = sta.apply(0, ind, a);
				out.println(v[0] + " " + v[1] + " " + v[2]);
				out.flush();
			}else if(sp[0].equals("gb")){
				int ind = Integer.parseInt(sp[1]);
				int[] v = stb.apply(0, n-ind, b);
//				for(int j = 0;j < n;j++){
//					tr(stx.node[stx.H+j].A);
//					tr(stx.node[stx.H+j].B);
//					tr(stx.node[stx.H+j].Y);
//				}
				
				int[][] w = stx.apply(0, n-ind, V);
//				tr(w);
				int[] wv = mul(w, sta.apply(0, ind+1, a));
				out.println((v[0]+wv[0])%mod + " " + (v[1]+wv[1])%mod);
				out.flush();
			}else{
				throw new RuntimeException();
			}
		}
	}
	
	public static int mod = 1000000007;
	public static long BIG = 8L*mod*mod;
	
	public static int[] mul(int[][] A, int[] v)
	{
		int m = A.length;
		int n = v.length;
		int[] w = new int[m];
		for(int i = 0;i < m;i++){
			long sum = 0;
			for(int k = 0;k < n;k++){
				sum += (long)A[i][k] * v[k];
				if(sum >= BIG)sum -= BIG;
			}
			w[i] = (int)(sum % mod);
		}
		return w;
	}
	
	public static class SegmentTreeMatrix {
		public int M, H, N;
		public int[][][] node;
		public static int mod = 1000000007;
		public static long BIG = 8L*mod*mod;
		public int S;
		
		public SegmentTreeMatrix(int n, int S)
		{
			N = n;
			M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
			H = M>>>1;
			this.S = S;
			
			node = new int[M][][];
			for(int i = 0;i < N;i++){
				node[H+i] = new int[S][S];
				for(int j = 0;j < S;j++){
					node[H+i][j][j] = 1;
				}
			}
			
			for(int i = H-1;i >= 1;i--)propagate(i);
		}
		
		private void propagate(int cur)
		{
			node[cur] = prop2(node[2*cur], node[2*cur+1], node[cur]);
		}
		
		private int[][] prop2(int[][] L, int[][] R, int[][] C)
		{
			if(L != null && R != null){
				C = mul(R, L, C, mod);
				return C;
			}else if(L != null){
				return prop1(L, C);
			}else if(R != null){
				return prop1(R, C);
			}else{
				return null;
			}
		}
		
		private int[][] prop1(int[][] L, int[][] C)
		{
			if(C == null){
//				C = L; // read only
				C = new int[S][];
				for(int i = 0;i < S;i++){
					C[i] = Arrays.copyOf(L[i], S);
				}
			}else{
				for(int i = 0;i < S;i++){
					C[i] = Arrays.copyOf(L[i], S);
				}
			}
			return C;
		}
		
		public void update(int pos) {
			for(int i = H+pos>>>1;i >= 1;i>>>=1)propagate(i);
		}
		
		public int[] apply(int l, int r, int[] v){
			return apply(l, r, 0, H, 1, v);
		}
		
		protected int[] apply(int l, int r, int cl, int cr, int cur, int[] v)
		{
			if(l <= cl && cr <= r){
				return mul(node[cur], v, mod);
			}else{
				int mid = cl+cr>>>1;
				if(cl < r && l < mid){
					v = apply(l, r, cl, mid, 2*cur, v);
				}
				if(mid < r && l < cr){
					v = apply(l, r, mid, cr, 2*cur+1, v);
				}
				return v;
			}
		}
		
		
		public static int[] mul(int[][] A, int[] v, int mod)
		{
			int m = A.length;
			int n = v.length;
			int[] w = new int[m];
			for(int i = 0;i < m;i++){
				long sum = 0;
				for(int k = 0;k < n;k++){
					sum += (long)A[i][k] * v[k];
					if(sum >= BIG)sum -= BIG;
				}
				w[i] = (int)(sum % mod);
			}
			return w;
		}
		
		public static int[][] mul(int[][] A, int[][] B, int[][] C, int mod)
		{
			int m = A.length;
			int n = A[0].length;
			int o = B[0].length;
			if(C == null)C = new int[m][o];
			for(int i = 0;i < m;i++){
				for(int j = 0;j < o;j++){
					long sum = 0;
					for(int k = 0;k < n;k++){
						sum += (long)A[i][k] * B[k][j];
						if(sum >= BIG)sum -= BIG;
					}
					sum %= mod;
					C[i][j] = (int)sum;
				}
			}
			return C;
		}
	}	
	
	
	public static class SegmentTreeNode {
		public int M, H, N;
		public Node[] node;
		public static int mod = 1000000007;
		public static long BIG = 8L*mod*mod;
		
		private static class Node
		{
			int[][] B;
			int[][] A;
			int[][] Y;
			
			public Node() {
				B = new int[2][2];
				A = new int[3][3];
				Y = new int[2][3];
			}
		}
		
		public SegmentTreeNode(int n)
		{
			N = n;
			M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
			H = M>>>1;
			
			node = new Node[M];
			for(int i = 0;i < N;i++){
				node[H+i] = new Node();
				for(int j = 0;j < 2;j++){
					for(int k = 0;k < 3;k++){
						node[H+i].Y[j][k] = 6*(n-1-i)+k+j*3;
					}
				}
				for(int j = 0;j < 2;j++){
					node[H+i].B[j][j] = 1;
				}
				for(int j = 0;j < 3;j++){
					node[H+i].A[j][j] = 1;
				}
			}
			for(int i = H-1;i >= 1;i--)propagate(i);
		}
		
		private void propagate(int cur)
		{
			node[cur] = prop2(node[2*cur], node[2*cur+1], node[cur]);
		}
		
		// B'(BXA+Y)A'+Z
		private Node prop2(Node L, Node R, Node C)
		{
			if(L != null && R != null){
				if(C == null)C = new Node();
				C.B = mul(R.B, L.B);
				C.A = mul(L.A, R.A);
				C.Y = add(mul(R.B, mul(L.Y, R.A)), R.Y);
				return C;
			}else if(L != null){
				return prop1(L, C);
			}else if(R != null){
				return prop1(R, C);
			}else{
				return null;
			}
		}
		
		private Node prop1(Node L, Node C)
		{
			if(C == null)C = new Node();
			C.B = L.B;
			C.A = L.A;
			C.Y = L.Y;
			return C;
		}
		
		public void update(int pos) {
			for(int i = H+pos>>>1;i >= 1;i>>>=1)propagate(i);
		}
		
		public static int[] mul(int[][] A, int[] v)
		{
			int m = A.length;
			int n = v.length;
			int[] w = new int[m];
			for(int i = 0;i < m;i++){
				long sum = 0;
				for(int k = 0;k < n;k++){
					sum += (long)A[i][k] * v[k];
					if(sum >= BIG)sum -= BIG;
				}
				w[i] = (int)(sum % mod);
			}
			return w;
		}
		
		public static int[][] mul(int[][] A, int[][] B)
		{
			assert A[0].length == B.length;
			int m = A.length;
			int n = A[0].length;
			int o = B[0].length;
			int[][] C = new int[m][o];
			for(int i = 0;i < m;i++){
				long[] sum = new long[o];
				for(int k = 0;k < n;k++){
					for(int j = 0;j < o;j++){
						sum[j] += (long)A[i][k] * B[k][j];
						if(sum[j] >= BIG)sum[j] -= BIG;
					}
				}
				for(int j = 0;j < o;j++){
					C[i][j] = (int)(sum[j] % mod);
				}
			}
			return C;
		}
		
		public static int[][] add(int[][] A, int[][] B)
		{
			assert A.length == B.length;
			assert A[0].length == B[0].length;
			int m = A.length;
			int n = A[0].length;
			int[][] C = new int[m][n];
			for(int i = 0;i < m;i++){
				for(int j = 0;j < n;j++){
					C[i][j] = (A[i][j] + B[i][j]) % mod;
				}
			}
			return C;
		}
		
		public int[][] apply(int l, int r, int[][] v){
			return apply(l, r, 0, H, 1, v);
		}
		
		protected int[][] apply(int l, int r, int cl, int cr, int cur, int[][] v)
		{
			if(l <= cl && cr <= r){
				return add(mul(mul(node[cur].B, v), node[cur].A), node[cur].Y);
			}else{
				int mid = cl+cr>>>1;
				if(cl < r && l < mid){
					v = apply(l, r, cl, mid, 2*cur, v);
				}
				if(mid < r && l < cr){
					v = apply(l, r, mid, cr, 2*cur+1, v);
				}
				return v;
			}
		}
	}	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		br = new BufferedReader(INPUT.isEmpty() ? new InputStreamReader(System.in) : new StringReader(INPUT));
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

yukicoder

結果

テストケース

ソースコード