結果

問題 No.426 往復漸化式
ユーザー uwiuwi
提出日時 2016-09-23 00:18:45
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 8,835 bytes
コンパイル時間 4,878 ms
コンパイル使用メモリ 89,448 KB
実行使用メモリ 227,908 KB
最終ジャッジ日時 2024-04-28 20:04:31
合計ジャッジ時間 40,225 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 114 ms
40,880 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
権限があれば一括ダウンロードができます

ソースコード

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;
	}
	
	// 
	
	// b2 = XA2A1A0a0
	// b1 = B2(XA2A1A0a0)+YA1A0a0
	// b1 = B1(B2(XA2A1A0a0)+YA1A0a0)+ZA0a0
	// B1(B2XA3+Y)A2+Z
	// B1B2*X*A3+YA2+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)
		{
			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[n];
				for(int k = 0;k < n;k++){
					for(int j = 0;j < n;j++){
						sum[j] += (long)A[i][k] * B[k][j];
						if(sum[j] >= BIG)sum[j] -= BIG;
					}
				}
				for(int j = 0;j < n;j++){
					C[i][j] = (int)(sum[j] % mod);
				}
			}
			return C;
		}
		
		public static int[][] add(int[][] A, int[][] B)
		{
			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