結果

問題 No.426 往復漸化式
ユーザー uwiuwi
提出日時 2016-09-23 00:48:34
言語 Java21
(openjdk 21)
結果
AC  
実行時間 2,333 ms / 5,000 ms
コード長 9,161 bytes
コンパイル時間 4,605 ms
コンパイル使用メモリ 85,936 KB
実行使用メモリ 224,136 KB
最終ジャッジ日時 2024-04-28 20:20:08
合計ジャッジ時間 39,474 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 112 ms
40,500 KB
testcase_01 AC 142 ms
41,900 KB
testcase_02 AC 141 ms
41,892 KB
testcase_03 AC 302 ms
47,276 KB
testcase_04 AC 302 ms
46,928 KB
testcase_05 AC 734 ms
70,816 KB
testcase_06 AC 738 ms
70,432 KB
testcase_07 AC 2,001 ms
199,080 KB
testcase_08 AC 1,956 ms
199,368 KB
testcase_09 AC 2,194 ms
200,416 KB
testcase_10 AC 2,201 ms
200,840 KB
testcase_11 AC 1,484 ms
194,848 KB
testcase_12 AC 1,931 ms
201,012 KB
testcase_13 AC 2,252 ms
209,764 KB
testcase_14 AC 1,971 ms
200,300 KB
testcase_15 AC 1,444 ms
195,048 KB
testcase_16 AC 1,785 ms
199,836 KB
testcase_17 AC 1,993 ms
200,440 KB
testcase_18 AC 1,824 ms
199,876 KB
testcase_19 AC 1,789 ms
199,552 KB
testcase_20 AC 1,990 ms
205,988 KB
testcase_21 AC 2,333 ms
224,136 KB
testcase_22 AC 1,968 ms
205,608 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

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)); }
}
0