結果

問題 No.510 二次漸化式
コンテスト
ユーザー kuuso1
提出日時 2017-05-03 01:45:35
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 795 ms / 3,000 ms
コード長 4,915 bytes
コンパイル時間 1,982 ms
コンパイル使用メモリ 111,616 KB
実行使用メモリ 97,776 KB
最終ジャッジ日時 2024-09-14 04:49:56
合計ジャッジ時間 19,963 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	const long mod = (long) 1e9 + 7;
	
	public void Solve(){
		
		var E = new MatMod(new long[][]{
			new long[] {1, 0, 0, 0},
			new long[] {0, 1, 0, 0},
			new long[] {0, 0, 1, 0},
			new long[] {0, 0, 0, 1}
			});
		
		var ST = new SegTree<MatMod>(N, E, (a, b) => b * a );
		
		var A = new MatMod(new long[][]{
			new long[] {1, 0, 0, 0},
			new long[] {0, 0, 0, 1},
			new long[] {0, 0, 0, 1},
			new long[] {0, 0, 0, 1}
			});
		ST.UniqInit(A);
		
		long[] v0 = new long[] {1, 1, 1, 1};
		
		for(int q=0;q<Q;q++){
			//ST.Dump();
			var ss = Query[q];
			int i = int.Parse(ss[1]);
			switch(ss[0][0]){
				case 'x':
					long v = long.Parse(ss[2]);
					var ai = new MatMod(ST.At(i));
					ai.A[0][2] = v;
					ST.Update(i,ai);
				break;
				
				case 'y':
					long vv = long.Parse(ss[2]); if(vv >= mod) vv %= mod;
					var aa = new MatMod(ST.At(i));
					aa.A[1][1] = vv;
					aa.A[2][1] = 2*vv;
					aa.A[2][2] = vv*vv % mod;
					ST.Update(i,aa);
				break;
				
				case 'a':
					var xx = ST.Query(0,i);
					long ans = (xx * v0)[0];
					Console.WriteLine(ans);
				break;
				
				default:
				break;
			}
		}
	}
	int N;
	int Q;
	String[][] Query;
	public Sol(){
		N = ri();
		Q = ri();
		Query = new String[Q][];
		for(int i=0;i<Q;i++) Query[i] = rsa();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}

struct MatMod{
	public long[][] A;
	const long mod = (long)1e9+7;
	const int N = 4;
	public MatMod(long[][] a){
		A = new long[N][];
		for(int i=0;i<N;i++){
			A[i] = new long[N];
			for(int j=0;j<N;j++){
				A[i][j] = a[i][j]; if(A[i][j] >= mod) A[i][j] %= mod;
			}
		}
	}
	public MatMod(MatMod a){
		A = new long[N][];
		for(int i=0;i<N;i++){
			A[i] = new long[N];
			for(int j=0;j<N;j++){
				A[i][j] = a.A[i][j];
			}
		}
	}
	
	
	static public MatMod operator * (MatMod a, MatMod b){
		long[][] c = new long[N][];
		for(int i=0;i<N;i++) c[i] = new long[N];
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				for(int k=0;k<N;k++){
					c[i][j] += a.A[i][k] * b.A[k][j];
					if(c[i][j] >= mod) c[i][j] %= mod;
				}
			}
		}
		return new MatMod(c);
	}
	static public long[] operator * (MatMod a, long[] v){
		long[] c = new long[N];
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				c[i] += a.A[i][j] * v[j];
				if(c[i] >= mod) c[i] %= mod;
			}
		}
		return c;
	}
	public override String ToString(){
		return "{" + String.Join(" ",A.Select(ar => "[" + String.Join(" ",ar) + "]")) + "}"; 
	}

}


class SegTree<T>{
	//segment Tree 
	// 0-origin
	T[] Data;	
	T Ini;
	Func<T,T,T> Op;
	int N;
	int n;
	
	//コンストラクタ
	public SegTree(int n_,T ini_, Func<T,T,T> op_){
		N = n_;
		Ini = ini_;
		n = 1;
		while(n < n_) n *= 2;
		Data = new T[2*n - 1];
		for(int i=0;i<2*n-1;i++) Data[i] = Ini;
		Op = op_;
	}
	
	//k-番目の値をaに変更
	//	   0
	//	 1   2
	//	3 4 5 6
	public void Update(int k,T a){
		k += n-1;	//上にはn-1個乗る
		Data[k] = a;
		while(k > 0){
			k = (k-1) / 2;
			Data[k] = Op(Data[k*2+1],Data[k*2+2]);
		}
	}
	
	//Query;
	//	[a,b) のOp(...)を返す
	//	後ろ3つの引数は	k,l,r：ヒープのk-ノードが範囲 [l,r) に対応していることを示す
	//	外から呼ぶ時は Query(a,b,0,0,n) の形で呼ぶ
	public T Query(int a, int b){
		return Query(a, b, 0, 0, n);
	}
	
	public T Query(int a,int b,int k,int l,int r){
		// [a,b) ∩ [l,r) =φ　⇒Iniを返す
		if(r<=a || b<=l) return Ini;
		// [a,b) ⊃ [l,r) ⇒Data[k]を返す 
		if(a<=l && r<=b)return Data[k];
		// さもなくば、Op(l,r)を返す
		T vl = Query(a,b,k*2+1,l,(l+r)/2);
		T vr = Query(a,b,k*2+2,(l+r)/2,r);
		return Op(vl, vr);
	}
	
	public void UniqInit(T a){
		for(int i=0;i<N;i++){
			Data[i + (n-1)] = a;
		}
		for(int i=n-2;i>=0;i--){
			Data[i] = Op(Data[i*2+1], Data[i*2+2]);
		}
	}
	public void UniqUnit(T unit){
		for(int i=0;i<n;i++){
			Data[i + (n-1)] = unit;
		}
	}
	
	public T At(int i){
		return Data[i + (n-1)];
	}
	
	public void Dump(){
		Console.WriteLine();
		int h = 0;
		int cnt = 0;
		for(int i=0;i<Data.Length;i++){
			Console.Write("{0} ",Data[i].ToString());
			cnt++;
			if(cnt == 1<<h){
				cnt = 0;
				h++;
				Console.WriteLine();
			}
		}
	}
	
}
0