結果
| 問題 | No.426 往復漸化式 |
| ユーザー |
 uwi
|
| 提出日時 | 2016-09-23 00:18:45 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,835 bytes |
| コンパイル時間 | 4,834 ms |
| コンパイル使用メモリ | 89,728 KB |
| 実行使用メモリ | 235,316 KB |
| 最終ジャッジ日時 | 2024-11-17 15:18:51 |
| 合計ジャッジ時間 | 36,736 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 106 ms
53,480 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 | - |
ソースコード
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)); }
}