結果

問題 No.426 往復漸化式
ユーザー 37zigen37zigen
提出日時 2016-09-30 01:14:13
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,473 ms / 5,000 ms
コード長 8,174 bytes
コンパイル時間 4,698 ms
コンパイル使用メモリ 95,388 KB
実行使用メモリ 116,200 KB
最終ジャッジ日時 2023-08-13 15:11:02
合計ジャッジ時間 19,242 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 81 ms
52,932 KB
testcase_01 AC 106 ms
54,868 KB
testcase_02 AC 105 ms
54,788 KB
testcase_03 AC 267 ms
70,308 KB
testcase_04 AC 271 ms
68,744 KB
testcase_05 AC 647 ms
82,664 KB
testcase_06 AC 651 ms
83,472 KB
testcase_07 AC 733 ms
91,284 KB
testcase_08 AC 697 ms
84,348 KB
testcase_09 AC 1,213 ms
116,200 KB
testcase_10 AC 1,271 ms
114,884 KB
testcase_11 AC 289 ms
68,816 KB
testcase_12 AC 358 ms
74,092 KB
testcase_13 AC 1,294 ms
115,840 KB
testcase_14 AC 475 ms
75,440 KB
testcase_15 AC 418 ms
72,376 KB
testcase_16 AC 590 ms
72,272 KB
testcase_17 AC 1,473 ms
109,888 KB
testcase_18 AC 578 ms
72,524 KB
testcase_19 AC 227 ms
58,332 KB
testcase_20 AC 273 ms
60,192 KB
testcase_21 AC 794 ms
105,980 KB
testcase_22 AC 273 ms
60,064 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package No400番台;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;

public class Q426 {
	public static void main(String[] args) {
		new Q426().run();
	}

	final long MOD = 1_000_000_000 + 7;

	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";

	void run() {
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		solver();
		out.flush();
	}

	void solver() {
		int n = ni();
		long[][] a_0 = { { nl() }, { nl() }, { nl() } };
		long[][] b_n = { { nl() }, { nl() } };
		int q = ni();
		String[] s = new String[q];
		int[][] x = new int[q][];
		int[] shrink = new int[q];
		long[][][]as = new long[ q][][];
		long[][][] bs = new long[q][][];
		for (int i = 0; i < q; i++) {
			s[i] = ns();
			shrink[i] = ni();
			x[i] = new int[] { shrink[i], i };
			if (s[i].equals("a")) {
				as[i] = new long[][] { { nl(), nl(), nl() }, { nl(), nl(), nl() }, { nl(), nl(), nl() } };
			} else if (s[i].equals("b")) {
				bs[i] = new long[][] { { nl(), nl() }, { nl(), nl() } };
			}
		}
		Arrays.sort(x, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o1[0], o2[0]);
			}
		});

		int pos = -1;
		int[] ref = new int[2 * q + 1];
		Arrays.fill(ref, -1);
		for (int i = 0; i < q; i++) {
			if (i == 0 || x[i][0] != x[i - 1][0]) {
				if (i == 0 && x[i][0] != 0)
					pos += 2;
				else if (i == q - 1 && x[i][0] != n)
					pos += 2;
				else if (i != 0 && x[i][0] != x[i - 1][0] + 1)
					pos += 2;
				else if (i == 0 && x[i][0] == 0)
					pos += 1;
				else if (i != 0 && x[i][0] != x[i - 1][0])
					pos += 1;
			}
			shrink[x[i][1]] = pos;
			ref[pos] = x[i][0];
		}
		if (x[q - 1][0] != n)
			pos++;
		pos++;
		ref = Arrays.copyOf(ref, pos);
		SegmentTree seg = new SegmentTree(Arrays.copyOf(ref, pos), n);
		for (int i = 0; i < q; i++) {
			if (s[i].equals("a")) {
				seg.set(shrink[i], as[i], 0);
			} else if (s[i].equals("b")) {
				seg.set(shrink[i], bs[i], 1);
			} else if (s[i].equals("ga")) {
				print(seg.geta(i, a_0, shrink));
			} else if (s[i].equals("gb")) {
				if (shrink[i] == pos - 1) {
					print(b_n);
				} else
					print(seg.getb(i, a_0, b_n, shrink));
			}
		}
	}
	void print(long[][] a){
		for(int i=0;i<a.length;i++){
			System.out.print(a[i][0]+(i==a.length-1?"\n":" "));
		}
	}

	class SegmentTree {
		int n = 1;
		long[][][][] node;

		public SegmentTree(int[] ref, int N) {
			int n_ = ref.length;
			while (n < n_)
				n *= 2;
			node = new long[2 * n - 1][3][][];
			for (int i = 0; i < 2 * n - 1; i++) {
				node[i][0] = new long[][] { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } };
				node[i][1] = new long[][] { { 1, 0 }, { 0, 1 } };
			}
			for (int i = 0; i < n_; i++) {
				if (ref[i] == -1) {
					int post = (i == n_ - 1 ? N + 1 : ref[i + 1]);
					int pre = (i == 0 ? -1 : ref[i - 1]);
					node[i + n - 1][2] = init(pre + 1, post - 1);
				} else {
					node[i + n - 1][2] = init(ref[i], ref[i]);
				}
			}
			for (int i = n - 2; i >= 0; i--) {
				node[i][2] = merge(node[2 * i + 1], node[2 * i + 2])[2];
			}
		}

		long[][] init(long a, long b) {
			long sum1 = (b - a + 1) % MOD * (b + a) % MOD * inv2 % MOD;
			long sum2 = b - a + 1;
			return new long[][] { { 6L * sum1, 6L * sum1 + 1 * sum2, 6L * sum1 + 2 * sum2 },
					{ 6L * sum1 + 3L * sum2, 6L * sum1 + 4L * sum2, 6L * sum1 + 5L * sum2 } };
		}

		void set(int k, long[][] val, int mode) {
			k += n - 1;
			node[k][mode] = val;
			while (k > 0) {
				k = (k - 1) / 2;
				node[k] = merge(node[2 * k + 1], node[2 * k + 2]);
			}
		}

		long[][][] query(int a, int b) {
			return query(a, b, 0, n, 0);
		}

		long[][][] query(int a, int b, int l, int r, int k) {
			if (r <= a || b <= l) {
				return new long[][][] { { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } }, { { 1, 0 }, { 0, 1 } }, null  };
			} else if (a <= l && r <= b) {
				return node[k];
			} else {
				long[][][] vl = query(a, b, l, (l + r) / 2, 2 * k + 1);
				long[][][] vr = query(a, b, (l + r) / 2, r, 2 * k + 2);
				return merge(vl, vr);
			}
		}

		long[][][] merge(long[][][] vl, long[][][] vr) {
			long[][][] ret = new long[][][] { mul(vr[0], vl[0]), mul(vl[1], vr[1]), null };
			if (vl[2] == null && vr[2] == null)
				ret[2] = null;
			else if (vl[2] == null)
				ret[2] = vr[2];
			else if (vr[2] == null)
				ret[2] = vl[2];
			else
				ret[2] = sum(vl[2], mul(mul(vl[1], vr[2]), vl[0]));
			return ret;
		}

		long[][] geta(int i, long[][] a_0, int[] shrink) {
			return mul(query(0, shrink[i] - 1 + 1)[0], a_0);
		}

		long[][] getb(int i, long[][] a_0, long[][] b_n, int[] shrink) {
			return sum(mul(query(shrink[i] + 1, n + 1)[1], b_n),
					mul(mul(query(shrink[i]+1, n + 1)[2], query(0, shrink[i] + 1)[0]), a_0));
		}

	}

	long[][] sum(long[][] A, long[][] B) {
		long[][] C = new long[A.length][A[0].length];
		for (int i = 0; i < A.length; i++) {
			for (int j = 0; j < A[0].length; j++) {
				C[i][j] = (A[i][j] % MOD + B[i][j] % MOD) % MOD;
			}
		}
		return C;
	}

	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] % MOD * B[k][j] % MOD;
					C[i][j] %= MOD;
				}
			}
		}
		return C;
	}

	long inv2 = inv(2, MOD);

	long inv(long a, long mod) {
		a = a % mod;
		long b = mod;
		long p = 1, q = 0;
		while (b > 1) {
			long c = b / a;
			b = b % a;
			q = q - p * c;
			long d = b;
			b = a;
			a = d;
			d = p;
			p = q;
			q = d;
		}
		while (q < 0)
			q += mod;
		return q;
	}

	static long nl() {
		try {
			long num = 0;
			boolean minus = false;
			while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'))
				;
			if (num == '-') {
				num = 0;
				minus = true;
			} else {
				num -= '0';
			}

			while (true) {
				int b = is.read();
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
			}
		} catch (IOException e) {
		}
		return -1;
	}

	static char nc() {
		try {
			int b = skip();
			if (b == -1)
				return 0;
			return (char) b;
		} catch (IOException e) {
		}
		return 0;
	}

	static double nd() {
		try {
			return Double.parseDouble(ns());
		} catch (Exception e) {
		}
		return 0;
	}

	static String ns() {
		try {
			int b = skip();
			StringBuilder sb = new StringBuilder();
			if (b == -1)
				return "";
			sb.append((char) b);
			while (true) {
				b = is.read();
				if (b == -1)
					return sb.toString();
				if (b <= ' ')
					return sb.toString();
				sb.append((char) b);
			}
		} catch (IOException e) {
		}
		return "";
	}

	public static char[] ns(int n) {
		char[] buf = new char[n];
		try {
			int b = skip(), p = 0;
			if (b == -1)
				return null;
			buf[p++] = (char) b;
			while (p < n) {
				b = is.read();
				if (b == -1 || b <= ' ')
					break;
				buf[p++] = (char) b;
			}
			return Arrays.copyOf(buf, p);
		} catch (IOException e) {
		}
		return null;
	}

	public static byte[] nse(int n) {
		byte[] buf = new byte[n];
		try {
			int b = skip();
			if (b == -1)
				return null;
			is.read(buf);
			return buf;
		} catch (IOException e) {
		}
		return null;
	}

	static int skip() throws IOException {
		int b;
		while ((b = is.read()) != -1 && !(b >= 33 && b <= 126))
			;
		return b;
	}

	static boolean eof() {
		try {
			is.mark(1000);
			int b = skip();
			is.reset();
			return b == -1;
		} catch (IOException e) {
			return true;
		}
	}

	static int ni() {
		try {
			int num = 0;
			boolean minus = false;
			while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'))
				;
			if (num == '-') {
				num = 0;
				minus = true;
			} else {
				num -= '0';
			}

			while (true) {
				int b = is.read();
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
			}
		} catch (IOException e) {
		}
		return -1;
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

}
0