結果

問題 No.621 3 x N グリッド上のドミノの置き方の数
ユーザー kuuso1kuuso1
提出日時 2017-12-21 22:44:01
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 663 ms / 3,000 ms
コード長 5,434 bytes
コンパイル時間 2,438 ms
コンパイル使用メモリ 117,936 KB
実行使用メモリ 29,024 KB
最終ジャッジ日時 2024-05-10 02:39:49
合計ジャッジ時間 31,999 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 113 ms
29,024 KB
testcase_01 AC 141 ms
22,656 KB
testcase_02 AC 23 ms
18,688 KB
testcase_03 AC 113 ms
22,272 KB
testcase_04 AC 118 ms
22,400 KB
testcase_05 AC 123 ms
22,272 KB
testcase_06 AC 123 ms
22,528 KB
testcase_07 AC 128 ms
22,272 KB
testcase_08 AC 128 ms
22,272 KB
testcase_09 AC 133 ms
22,656 KB
testcase_10 AC 129 ms
22,272 KB
testcase_11 AC 132 ms
22,144 KB
testcase_12 AC 151 ms
22,656 KB
testcase_13 AC 181 ms
22,956 KB
testcase_14 AC 200 ms
22,972 KB
testcase_15 AC 229 ms
23,100 KB
testcase_16 AC 247 ms
23,352 KB
testcase_17 AC 256 ms
23,116 KB
testcase_18 AC 300 ms
22,708 KB
testcase_19 AC 325 ms
23,096 KB
testcase_20 AC 342 ms
22,580 KB
testcase_21 AC 343 ms
23,096 KB
testcase_22 AC 406 ms
22,832 KB
testcase_23 AC 395 ms
23,196 KB
testcase_24 AC 418 ms
23,100 KB
testcase_25 AC 470 ms
23,112 KB
testcase_26 AC 472 ms
22,844 KB
testcase_27 AC 512 ms
22,996 KB
testcase_28 AC 522 ms
22,968 KB
testcase_29 AC 547 ms
23,096 KB
testcase_30 AC 539 ms
23,096 KB
testcase_31 AC 527 ms
22,984 KB
testcase_32 AC 517 ms
22,960 KB
testcase_33 AC 538 ms
22,976 KB
testcase_34 AC 529 ms
22,840 KB
testcase_35 AC 525 ms
23,116 KB
testcase_36 AC 538 ms
23,104 KB
testcase_37 AC 554 ms
22,836 KB
testcase_38 AC 575 ms
23,100 KB
testcase_39 AC 572 ms
23,256 KB
testcase_40 AC 572 ms
22,968 KB
testcase_41 AC 542 ms
22,696 KB
testcase_42 AC 544 ms
22,836 KB
testcase_43 AC 559 ms
22,968 KB
testcase_44 AC 570 ms
22,836 KB
testcase_45 AC 570 ms
22,956 KB
testcase_46 AC 574 ms
23,328 KB
testcase_47 AC 569 ms
22,840 KB
testcase_48 AC 572 ms
23,052 KB
testcase_49 AC 573 ms
22,988 KB
testcase_50 AC 576 ms
23,220 KB
testcase_51 AC 570 ms
22,860 KB
testcase_52 AC 574 ms
22,844 KB
testcase_53 AC 574 ms
22,964 KB
testcase_54 AC 579 ms
23,092 KB
testcase_55 AC 572 ms
22,852 KB
testcase_56 AC 579 ms
23,216 KB
testcase_57 AC 576 ms
22,860 KB
testcase_58 AC 584 ms
23,208 KB
testcase_59 AC 663 ms
22,972 KB
testcase_60 AC 655 ms
22,836 KB
testcase_61 AC 660 ms
22,968 KB
testcase_62 AC 660 ms
22,968 KB
testcase_63 AC 663 ms
22,976 KB
testcase_64 AC 393 ms
22,952 KB
testcase_65 AC 399 ms
22,848 KB
testcase_66 AC 398 ms
22,816 KB
testcase_67 AC 400 ms
22,836 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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(){
		if(N == 1){
			Console.WriteLine(2);
			return;
		}
		// B * A^(N-1) * v;
		
		int NN = 1 << 6;
		EdgeA = new bool[NN,NN];
		EdgeB = new bool[NN,NN];
		tot = 0;
		int[] ar = new int[H * W];
		dfs(ar, 0 , 1);
		//Console.WriteLine(tot);
		
		long[][] e0 = new long[NN][];
		for(int i=0;i<NN;i++){
			e0[i] = new long[NN];
			e0[i][i] = 1;
		}
		Mat E = new Mat(e0);
		
		long[][] a0 = new long[NN][];
		for(int i=0;i<NN;i++){
			a0[i] = new long[NN];
		}
		long[][] b0 = new long[NN][];
		for(int i=0;i<NN;i++){
			b0[i] = new long[NN];
		}
		for(int i=0;i<NN;i++){
			for(int j=0;j<NN;j++){
				if(EdgeA[i,j]) a0[j][i] = 1;
				if(EdgeB[i,j]) b0[j][i] = 1;
			}
		}
		Mat A = new Mat(a0);
		Mat B = new Mat(b0);
		
//Console.WriteLine(A);
//Console.WriteLine(B);
		
		
		
		long[] v = new long[NN];
		v[NN-1] = 1;
		
		long k = N - 1;
		var x = A;
		var ret = E;
		while(k > 0){
			if((k & 1) == 1){
				ret *= x;
			}
			x *= x;
			k>>=1;
		}
		
		var C = B * ret;
		var Cv = C * v;
		long ans = Cv.Sum() % mod; if(ans < 0) ans += mod;
		Console.WriteLine(ans);
		
	}
	
	bool[,] EdgeA;
	bool[,] EdgeB;
	int tot;
	int H = 3, W = 7;
	
	void dfs(int[] ar, int now, int cnt){
		if(now == H * W){
			bool chk = true;
			for(int i=0;i<H;i++){
				for(int j=0;j<W;j++){
					if(InRange(i + 1, 0, H) && ar[i * W + j] == 0 && ar[(i + 1) * W + j] == 0) chk = false;
					if(InRange(j + 1, 0, W) && ar[i * W + j] == 0 && ar[i * W + j + 1] == 0) chk = false;
				}
			}
			if(chk){
				tot++;
				
				for(int j=0;j+2<W;j++){
					
					int[,] b = new int[3,3];
					for(int ii=0;ii<3;ii++){
						for(int jj=0;jj<2;jj++){
							if(InRange(ii+1,0,3) && ar[ii * W + j + jj] != 0 && ar[(ii + 1) * W + j + jj] == ar[ii * W + j + jj]) b[ii,jj] = b[ii+1,jj] = 1;
							if(InRange(jj+1,0,2) && ar[ii * W + j + jj] != 0 && ar[ii * W + j + jj + 1] == ar[ii * W + j + jj])   b[ii,jj] = b[ii,jj+1] = 1;
							if(jj == 0 && ar[ii * W + j + jj] != 0) b[ii,jj] = 1;
						}
					}
					int fr = 0;
					for(int jj=0;jj<2;jj++){
						for(int ii=0;ii<3;ii++){
							int num = jj * 3 + ii;
							if(b[ii,jj] == 1) fr |= (1 << num);
						}
					}
					
					b = new int[3,3];
					for(int ii=0;ii<3;ii++){
						if(ar[ii * W + j + 1] != 0 && ar[ii * W + j + 1] == ar[ii * W + j + 2]) b[ii,1] = b[ii,2] = 1;
						if(ii < 2 && ar[ii * W + j + 2] != 0 &&  ar[ii * W + j + 2] == ar[(ii + 1) * W + j + 2]) b[ii,2] = b[ii+1,2] = 1;
						if(ar[ii * W + j + 1] != 0) b[ii,1] = 1;
					}
					
					int to = 0;
					for(int jj=0;jj<2;jj++){
						for(int ii=0;ii<3;ii++){
							int num = jj * 3 + ii;
							if(b[ii,jj + 1] == 1) to |= (1 << num);
						}
					}
//if(fr == 0x3F) Console.WriteLine(to);
//for(int ii=0;ii<3;ii++){ for(int jj=0;jj<3;jj++) Console.Write("{0}",b[ii,jj]);Console.WriteLine();}Console.WriteLine();					
					
					EdgeA[fr, to] = true;
					if(j == W - 3) EdgeB[fr, to] = true;
				}
				
			}
			return;
		}
		
		dfs(ar, now + 1, cnt);
		int r = now / W, c = now % W;
		if(InRange(r + 1, 0, H) && ar[now] == 0 && ar[now + W] == 0){
			ar[now] = cnt; ar[now + W] = cnt;
			dfs(ar, now + 1, cnt + 1);
			ar[now] = 0; ar[now + W] = 0;
		}
		if(InRange(c + 1, 0, W) && ar[now] == 0 && ar[now + 1] == 0){
			ar[now] = cnt; ar[now + 1] = cnt;
			dfs(ar, now + 1, cnt + 1);
			ar[now] = 0; ar[now + 1] = 0;
		}
	}
	
	
	
	
	
	
	bool InRange(int t, int l, int r){
		return l <= t && t < r;
	}
	
	long N;
	public Sol(){
		N = rl();
	}

	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));}
}

class Mat{
	const int N = 1<<6;
	long[][] m;
	const long mod = (long) 1e9 + 7;
	
	public Mat(){
		m = new long[N][];
		for(int i=0;i<N;i++) m[i] = new long[N];
	}
	public Mat(long[][] ma){
		m = new long[N][];
		for(int i=0;i<N;i++){
			m[i] = new long[N];
			for(int j=0;j<N;j++) m[i][j] = ma[i][j];
		}
	}
	
	public static Mat operator * (Mat maa, Mat mab){
		long[][] ma = maa.m;
		long[][] mb = mab.m;
		
		long[][] mc = new long[N][];
		for(int i=0;i<N;i++) mc[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++){
					mc[i][j] += ma[i][k] * mb[k][j];
					mc[i][j] %= mod;
				}
				if(mc[i][j] < 0) mc[i][j] += mod;
			}
		}
		return new Mat(mc);
	}
	
	public static long[] operator * (Mat maa, long[] v){
		long[][] ma = maa.m;
		var ret = new long[N];
		for(int i=0;i<N;i++){
			for(int k=0;k<N;k++){
				ret[i] += ma[i][k] * v[k];
				ret[i] %= mod;
			}
			if(ret[i] < 0) ret[i] %= mod;
		}
		return ret;
	}
		
	public override String ToString(){
		var sb = new StringBuilder();
		for(int i=0;i<N;i++) sb.AppendLine(String.Join(" ",m[i]));
		return sb.ToString();
	}
}
0