結果
| 問題 | No.426 往復漸化式 |
| ユーザー |
 uwi
|
| 提出日時 | 2016-09-23 00:48:34 |
| 言語 | Java (openjdk 23) |
| 結果 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 22 |
ソースコード
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+Zstatic 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 onlyC = 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'+Zprivate 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)); }}