結果

問題 No.621 3 x N グリッド上のドミノの置き方の数
ユーザー kuuso1kuuso1
提出日時 2017-12-21 22:44:01
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 650 ms / 3,000 ms
コード長 5,434 bytes
コンパイル時間 2,727 ms
コンパイル使用メモリ 116,172 KB
実行使用メモリ 31,364 KB
最終ジャッジ日時 2024-12-17 22:52:54
合計ジャッジ時間 32,453 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 112 ms
26,864 KB
testcase_01 AC 139 ms
26,840 KB
testcase_02 AC 22 ms
22,580 KB
testcase_03 AC 113 ms
26,876 KB
testcase_04 AC 117 ms
27,100 KB
testcase_05 AC 121 ms
27,116 KB
testcase_06 AC 119 ms
26,856 KB
testcase_07 AC 124 ms
28,896 KB
testcase_08 AC 120 ms
27,112 KB
testcase_09 AC 129 ms
26,868 KB
testcase_10 AC 127 ms
28,916 KB
testcase_11 AC 126 ms
26,976 KB
testcase_12 AC 148 ms
29,156 KB
testcase_13 AC 176 ms
29,064 KB
testcase_14 AC 202 ms
29,188 KB
testcase_15 AC 227 ms
30,984 KB
testcase_16 AC 246 ms
27,036 KB
testcase_17 AC 255 ms
30,980 KB
testcase_18 AC 292 ms
28,812 KB
testcase_19 AC 314 ms
29,064 KB
testcase_20 AC 344 ms
31,136 KB
testcase_21 AC 346 ms
28,808 KB
testcase_22 AC 398 ms
30,984 KB
testcase_23 AC 390 ms
28,836 KB
testcase_24 AC 409 ms
29,056 KB
testcase_25 AC 469 ms
30,736 KB
testcase_26 AC 460 ms
27,040 KB
testcase_27 AC 509 ms
28,940 KB
testcase_28 AC 518 ms
26,760 KB
testcase_29 AC 538 ms
28,928 KB
testcase_30 AC 539 ms
28,812 KB
testcase_31 AC 529 ms
31,108 KB
testcase_32 AC 518 ms
31,004 KB
testcase_33 AC 537 ms
28,940 KB
testcase_34 AC 533 ms
31,236 KB
testcase_35 AC 516 ms
27,040 KB
testcase_36 AC 529 ms
30,984 KB
testcase_37 AC 540 ms
29,344 KB
testcase_38 AC 568 ms
31,236 KB
testcase_39 AC 570 ms
28,964 KB
testcase_40 AC 573 ms
31,120 KB
testcase_41 AC 578 ms
31,108 KB
testcase_42 AC 581 ms
30,988 KB
testcase_43 AC 561 ms
30,980 KB
testcase_44 AC 558 ms
28,944 KB
testcase_45 AC 570 ms
31,236 KB
testcase_46 AC 572 ms
29,312 KB
testcase_47 AC 572 ms
29,060 KB
testcase_48 AC 570 ms
26,884 KB
testcase_49 AC 567 ms
30,988 KB
testcase_50 AC 580 ms
29,060 KB
testcase_51 AC 570 ms
30,884 KB
testcase_52 AC 577 ms
30,856 KB
testcase_53 AC 576 ms
31,260 KB
testcase_54 AC 581 ms
29,068 KB
testcase_55 AC 575 ms
28,956 KB
testcase_56 AC 579 ms
31,364 KB
testcase_57 AC 568 ms
30,988 KB
testcase_58 AC 578 ms
29,044 KB
testcase_59 AC 648 ms
29,184 KB
testcase_60 AC 645 ms
28,800 KB
testcase_61 AC 642 ms
28,932 KB
testcase_62 AC 650 ms
31,112 KB
testcase_63 AC 650 ms
28,824 KB
testcase_64 AC 395 ms
30,976 KB
testcase_65 AC 386 ms
31,244 KB
testcase_66 AC 395 ms
30,860 KB
testcase_67 AC 396 ms
28,816 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