結果

問題 No.621 3 x N グリッド上のドミノの置き方の数
ユーザー kuuso1
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 66
権限があれば一括ダウンロードができます
コンパイルメッセージ
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