結果

問題 No.569 3 x N グリッドのパスの数
ユーザー fgwiebfaoishfgwiebfaoish
提出日時 2024-04-23 23:01:29
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 184 ms / 2,000 ms
コード長 14,954 bytes
コンパイル時間 3,331 ms
コンパイル使用メモリ 116,096 KB
実行使用メモリ 24,064 KB
最終ジャッジ日時 2024-04-23 23:01:41
合計ジャッジ時間 9,692 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
23,552 KB
testcase_01 AC 40 ms
23,552 KB
testcase_02 AC 43 ms
23,680 KB
testcase_03 AC 45 ms
23,424 KB
testcase_04 AC 43 ms
23,680 KB
testcase_05 AC 42 ms
23,296 KB
testcase_06 AC 45 ms
23,680 KB
testcase_07 AC 45 ms
23,424 KB
testcase_08 AC 46 ms
23,552 KB
testcase_09 AC 45 ms
23,552 KB
testcase_10 AC 45 ms
23,552 KB
testcase_11 AC 46 ms
23,680 KB
testcase_12 AC 45 ms
23,424 KB
testcase_13 AC 46 ms
23,552 KB
testcase_14 AC 48 ms
23,680 KB
testcase_15 AC 47 ms
23,680 KB
testcase_16 AC 48 ms
23,296 KB
testcase_17 AC 48 ms
23,552 KB
testcase_18 AC 48 ms
23,680 KB
testcase_19 AC 51 ms
23,296 KB
testcase_20 AC 113 ms
23,680 KB
testcase_21 AC 109 ms
23,680 KB
testcase_22 AC 109 ms
24,064 KB
testcase_23 AC 108 ms
23,680 KB
testcase_24 AC 110 ms
23,808 KB
testcase_25 AC 108 ms
24,064 KB
testcase_26 AC 108 ms
23,936 KB
testcase_27 AC 109 ms
23,808 KB
testcase_28 AC 110 ms
23,808 KB
testcase_29 AC 108 ms
23,808 KB
testcase_30 AC 110 ms
23,808 KB
testcase_31 AC 109 ms
23,680 KB
testcase_32 AC 110 ms
23,936 KB
testcase_33 AC 107 ms
23,680 KB
testcase_34 AC 107 ms
23,808 KB
testcase_35 AC 110 ms
23,680 KB
testcase_36 AC 108 ms
23,936 KB
testcase_37 AC 107 ms
24,064 KB
testcase_38 AC 108 ms
23,808 KB
testcase_39 AC 109 ms
23,936 KB
testcase_40 AC 182 ms
24,064 KB
testcase_41 AC 180 ms
23,936 KB
testcase_42 AC 182 ms
23,808 KB
testcase_43 AC 179 ms
23,936 KB
testcase_44 AC 179 ms
24,064 KB
testcase_45 AC 179 ms
23,808 KB
testcase_46 AC 180 ms
23,936 KB
testcase_47 AC 179 ms
24,064 KB
testcase_48 AC 178 ms
23,936 KB
testcase_49 AC 180 ms
23,808 KB
testcase_50 AC 180 ms
23,808 KB
testcase_51 AC 181 ms
23,808 KB
testcase_52 AC 184 ms
24,064 KB
testcase_53 AC 180 ms
23,808 KB
testcase_54 AC 180 ms
23,680 KB
testcase_55 AC 180 ms
24,064 KB
testcase_56 AC 179 ms
23,936 KB
testcase_57 AC 180 ms
23,936 KB
testcase_58 AC 179 ms
23,936 KB
testcase_59 AC 183 ms
23,936 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.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
using System.Threading;
using System.Runtime.CompilerServices;
using System.Diagnostics;
static class Program {
	const long inf = long.MaxValue>>1;
	const int mod = (int)1e9+7;
	static Sc sc = new Sc();
	static void Main() {
		Pt pt = new Pt(Solve);
		pt.Sm();
	}
	static void Solve(Pt pt) {
		var n = sc.L;
		var ft = new Frontier(n+1,4);
		ft.Ce4();
		ft.Cc2();
		pt.Wl(ft.Mp());
	}
}
public class Frontier {
	const long inf = long.MaxValue>>1;
	const int mod = (int)1e9+7;
	public int w, gn, gm;
	public long h;
	public List<Dt> li;
	public long[][] ba;
	public Frontier(long h,int w) {
		this.h=h;
		Dt.w=this.w=w;
		gm=(w+1)>>1;
		gm=w;
		Dt.gn=gn=(int)Ceiling(Log(gm,2));
	}
	public long Dp() {
		var dp = Enumerable.Repeat(0L,li.Count).ToArray();
		dp[1]=1;
		for(int i = 0;i<h;i++) {
			var ndp = Enumerable.Repeat(0L,li.Count).ToArray();
			for(int j = 0;j<li.Count;j++) {
				if(dp[j]==0) { continue; }
				for(int k = 1;k<li.Count;k++) {
					if(ba[j][k]==0) continue;
					ndp[k]=(ndp[k]+dp[j]*ba[j][k])%mod;
				}
			}
			dp=ndp;
		}
		long ans = dp[15];
		return ans;
	}
	public long Mp() {
		var dp = Enumerable.Repeat(0L,li.Count).ToArray();
		dp[1]=1;
		return Mp2(dp,ba,h)[15];
	}
	long[] Mp2(long[] r,long[][] x,long e) {
		while(e>0) {
			if((e&1)>0) { r=Mm(x,r); }
			x=Mm(x,x);
			e>>=1;
		}
		return r;
	}
	long[] Mm(long[][] a,long[] b) {
		var q = new long[b.Length];
		for(int j = 0;j<a.Length;j++) {
			for(int k = 0;k<a.Length;k++) {
				q[j]=(q[j]+a[j][k]*b[k])%mod;
			}
		}
		return q;
	}
	long[][] Mm(long[][] a,long[][] b) {
		var q = new long[a.Length][];
		for(int j = 0;j<a.Length;j++) {
			q[j]=new long[b[0].Length];
			for(int i = 0;i<b[0].Length;i++) {
				for(int k = 0;k<a.Length;k++) { q[j][i]=(q[j][i]+a[j][k]*b[k][i])%mod; }
			}
		}
		return q;
	}
	public void Cc1() {
		ba=new long[li.Count][];
		var ia = new int[gm];
		for(int j = 0;j<li.Count;j++) {
			ba[j]=new long[li.Count];
			for(int k = 1;k<li.Count;k++) {
				int gb = 0;
				var b0 = false;
				var bb = li[j].n&li[k].n;
				if(j!=0&&bb==0) { continue; }
				Uf uf = new Uf(li[k].c+li[j].g);
				var o = -1;
				for(int l = 0;l<w;l++) {
					if(!li[k].Isu(l-1)&&li[k].Isu(l)) { ia[++o]=l; }
					if(((bb>>l)&1)==1) {
						int pg = li[j].Geg(l)+li[k].c;
						uf.Union(pg,o);
						gb|=1<<(pg-li[k].c);
						if(pg-li[k].c==0) { b0=true; }
					}
				}
				if(li[j].g>0&&!b0) { goto lb; }
				for(int i = 0;i<li[k].c;i++) {
					var g1 = li[k].Geg(ia[i]);
					for(int l = i+1;l<li[k].c;l++) {
						var g2 = li[k].Geg(ia[l]);
						if(g1==g2) {
							if(!uf.Same(i,l)) { goto lb; }
						}
						else if(uf.Same(i,l)) { goto lb; }
					}
					if(li[j].g>0&&g1==0&&!uf.Same(i,li[k].c)) { goto lb; }
				}
				ba[j][k]=1;
				break;
			lb:;
			}
		}
	}
	public void Cc2() {
		ba=new long[li.Count][];
		var ia = new int[gm];
		var mm = 1<<(w-1);
		for(int j = 0;j<li.Count;j++) {
			ba[j]=new long[li.Count];
			for(int k = 1;k<li.Count;k++) {
				for(int im = 0;im<mm;im++) {
					Uf uf = new Uf(li[k].c+li[j].g+w);
					var o = -1;
					for(int l = 0;l<w;l++) {
						int e = 0;
						if(li[k].Isu(l)) {
							e++;
							ia[++o]=l;
							uf.Union(l+li[k].c+li[j].g,o);
						}
						if(li[j].Isu(l)) {
							e++;
							int pg = li[j].Geg(l)+li[k].c;
							uf.Union(l+li[k].c+li[j].g,pg);
						}
						if(l!=w-1&&((im>>l)&1)==1)
						{
							e++;
							uf.Union(l+li[k].c+li[j].g,l+li[k].c+li[j].g+1);
						}
						if(l!=0&&((im>>(l-1))&1)==1)
						{
							e++;
							uf.Union(l+li[k].c+li[j].g,l+li[k].c+li[j].g-1);
						}
						if(e!=0&&e!=2) { goto lb; }
					}
					for(int i = 0;i<li[k].c;i++) {
						var g1 = li[k].Geg(ia[i]);
						for(int l = i+1;l<li[k].c;l++) {
							var g2 = li[k].Geg(ia[l]);
							if(g1==g2) {
								if(!uf.Same(i,l)) { goto lb; }
							}
							else if(uf.Same(i,l)) { goto lb; }
						}
					}
					for(int i = 0;i<li[j].g;i++) {
						var bo = false;
						for(int l = 0;l<li[k].c;l++) {
							if(uf.Same(li[k].c+i,l)) { bo=true; break; }
						}
						if(!bo) { goto lb; }
					}
					ba[j][k]+=1;
				lb:;
				}
			}
		}
	}
	public void Ce1() {
		int b = 1<<w;
		li=new List<Dt>();
		for(int i = 0;i<b;i++) {
			Fu(0,0,0,0);
			void Fu(int a,long p,int g,int c) {
				if(a==w) { li.Add(new Dt(i,p,g,c)); }
				else if(((i>>a)&1)==0) Fu(a+1,p,g,c);
				else if(a!=0&&((i>>(a-1))&1)==1) { Fu(a+1,p+((p<<gn)&(((1<<gn)-1)<<(a*gn))),g,c); }
				else {
					for(int j = 0;j<=g;j++) { Fu(a+1,p+(j<<(a*gn)),Max(g,j+1),c+1); }
				}
			}
		}
	}
	public void Ce2() {
		int b = 1<<w;
		li=new List<Dt>();
		for(int i = 0;i<b;i++) {
			Fu(0,0,0);
			void Fu(int a,long p,int c) {
				if(a==w) { li.Add(new Dt(i,p,1<<gn,c)); }
				else if(((i>>a)&1)==0) Fu(a+1,p,c);
				else if(a!=0&&((i>>(a-1))&1)==1) { Fu(a+1,p+((p<<gn)&(((1<<gn)-1)<<(a*gn))),c); }
				else {
					for(int j = 0;j<gm;j++) { Fu(a+1,p+(j<<(a*gn)),c+1); }
				}
			}
		}
	}
	public void Ce3() {
		int b = 1<<w;
		li=new List<Dt>();
		for(int i = 0;i<b;i++) {
			Fu(0,0,0,0);
			void Fu(int a,long p,int g,int c) {
				if(a==w) {
					li.Add(new Dt(i,p,g,c));
					for(int j = 1;j<g;j++) {
						var bp = p;
						for(int k = 0;k<w;k++) {
							if(((i>>k)&1)==0) { continue; }
							if(Geb(bp,k)==j) { bp=Seb(bp,k,0); }
							else if(Geb(bp,k)==0) { bp=Seb(bp,k,j); }
						}
						li.Add(new Dt(i,bp,g,c));
					}
				}
				else if(((i>>a)&1)==0) Fu(a+1,p,g,c);
				else if(a!=0&&((i>>(a-1))&1)==1) { Fu(a+1,p+((p<<gn)&(((1L<<gn)-1)<<(a*gn))),g,c); }
				else {
					for(int j = 0;j<=g;j++) { Fu(a+1,p+(((long)j)<<(a*gn)),Max(g,j+1),c+1); }
				}
			}
		}
	}
	public void Ce4() {
		int b = 1<<w;
		li=new List<Dt>();
		for(int i = 0;i<b;i++) {
			Fu(0,0,0,0);
			void Fu(int a,long p,int g,int c) {
				if(a==w) { li.Add(new Dt(i,p,g,c)); }
				else if(((i>>a)&1)==0) Fu(a+1,p,g,c);
				else {
					for(int j = 0;j<=g;j++) { Fu(a+1,p+(j<<(a*gn)),Max(g,j+1),c+1); }
				}
			}
		}
	}
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public int Geb(long b,int k) {
		return (int)((b>>(k*gn))&((1<<gn)-1));
	}
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public long Seb(long b,int k,long g) {
		b&=~(((1L<<gn)-1)<<(k*gn));
		return b+(g<<(k*gn));
	}
	public int Pc(int n) {
		n-=(n>>1)&0x55555555;
		n=(n&0x33333333)+((n>>2)&0x33333333);
		return ((n+(n>>4)&0xF0F0F0F)*0x1010101)>>24;
	}
	public class Dt {
		public static int w, gn;
		public int n, g, c;
		public long b;
		public Dt(int n,long b,int g,int c) {
			this.n=n;
			this.b=b;
			this.g=g;
			this.c=c;
		}
		[MethodImpl(MethodImplOptions.AggressiveInlining)]
		public int Geg(int k) { return (int)((b>>(k*gn))&((1<<gn)-1)); }
		[MethodImpl(MethodImplOptions.AggressiveInlining)]
		public bool Isu(int k) { return k>=0&&((n>>k)&1)==1; }
	}
}
public class Uf {
	private int[] arr, hi;
	public int all;
	public Uf(int n) {
		arr=new int[n];
		hi=new int[n];
		all=n;
		for(int i = 0;i<n;i++) { arr[i]=-1; }
	}
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public void Union(int a,int b) {
		a=Root(a);
		b=Root(b);
		if(a!=b) {
			if(hi[a]<hi[b]) { (a, b)=(b, a); }
			arr[a]+=arr[b];
			hi[a]=Max(hi[a],hi[b]+1);
			arr[b]=a;
			all--;
		}
	}
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public bool Same(int a,int b) { return Root(a)==Root(b); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public int Size(int a) { return -arr[Root(a)]; }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public int Root(int a) { return arr[a]<0 ? a : arr[a]=Root(arr[a]); }
}
public class Pt {
	private StringBuilder sb = new StringBuilder();
	public Pt(Action<Pt> f) { f(this); }
	public void W(int s) { sb.Append(s); }
	public void W(long s) { sb.Append(s); }
	public void W(double s) { sb.Append(s); }
	public void W(decimal s) { sb.Append(s); }
	public void W(char s) { sb.Append(s); }
	public void W(string s) { sb.Append(s); }
	public void W(object s) { sb.Append(s); }
	public void W(params object[] s) { sb.Append(string.Join(" ",s)); }
	public void Wl(int s) { sb.Append(s).AppendLine(); }
	public void Wl(long s) { sb.Append(s).AppendLine(); }
	public void Wl(double s) { sb.Append(s).AppendLine(); }
	public void Wl(decimal s) { sb.Append(s).AppendLine(); }
	public void Wl(char s) { sb.Append(s).AppendLine(); }
	public void Wl(string s) { sb.AppendLine(s); }
	public void Wl(object s) { sb.Append(s).AppendLine(); }
	public void Wl(IEnumerable<int> s) { sb.AppendLine(string.Join(" ",s)); }
	public void Wl(IEnumerable<long> s) { sb.AppendLine(string.Join(" ",s)); }
	public void Wl(IEnumerable<double> s) { sb.AppendLine(string.Join(" ",s)); }
	public void Wl(IEnumerable<string> s) { sb.AppendLine(string.Join(" ",s)); }
	public void Wl(params object[] s) { sb.AppendLine(string.Join(" ",s)); }
	public void Wl() { sb.AppendLine(); }
	public void Sm() { Console.Write(sb); }
	public void Op(StreamWriter sw) {
		sw.Write(sb);
		sw.Close();
	}
	public static bool operator ==(Pt a,Pt b) { return a.sb.ToString()==b.sb.ToString(); }
	public static bool operator !=(Pt a,Pt b) { return a.sb.ToString()!=b.sb.ToString(); }
	public override bool Equals(object obj) { return false; }
	public override int GetHashCode() { return 0; }
}
public class Sc {
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected virtual string Rl() { return Console.ReadLine(); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected virtual string[] Sp(string st) { return st.Split(); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	private T Ct<T>(string s) { return (T)Convert.ChangeType(s,typeof(T)); }
	public virtual int I { get { return int.Parse(Rl()); } }
	public virtual long L { get { return long.Parse(Rl()); } }
	public virtual double D { get { return double.Parse(Rl()); } }
	public virtual string S { get { return Rl(); } }
	public int[] Ia { get { return Array.ConvertAll(Sp(Rl()),int.Parse); } }
	public long[] La { get { return Array.ConvertAll(Sp(Rl()),long.Parse); } }
	public double[] Da { get { return Array.ConvertAll(Sp(Rl()),double.Parse); } }
	public string[] Sa { get { return Sp(Rl()); } }
	public object[] Oa { get { return Sp(Rl()); } }
	public int[] Ia2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),int.Parse); } }
	public int[] Ia3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),int.Parse); }
	public int[] Ia3(int a) { return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),int.Parse); }
	public long[] La2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),long.Parse); } }
	public long[] La3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),long.Parse); }
	public long[] La3(int a) { return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),long.Parse); }
	public double[] Da2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),double.Parse); } }
	public double[] Da3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),double.Parse); }
	public T[] Arr<T>(int n,Func<T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(); } return a; }
	public T[] Arr<T>(int n,Func<int,T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(i); } return a; }
	public T[] Arr<T>(int n,Func<string[],T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(Sp(Rl())); } return a; }
	public T[] Arr<T>(int n,Func<int,string[],T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(i,Sp(Rl())); } return a; }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T) Tp2<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T, T) Tp3<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T, T, T) Tp4<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T, T, T, T) Tp5<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3]), Ct<T>(s[4])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T, T, T, T, T) Tp6<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3]), Ct<T>(s[4]), Ct<T>(s[5])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T1, T2) Tp2<T1, T2>() { var s = Sp(Rl()); return (Ct<T1>(s[0]), Ct<T2>(s[1])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T1, T1, T2) Tp3<T1, T2>() { var s = Sp(Rl()); return (Ct<T1>(s[0]), Ct<T1>(s[1]), Ct<T2>(s[2])); }
}
public class Scr:Sc {
	private List<string> li = new List<string>();
	private int l = 0;
	private bool bo = false;
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected override string Rl() {
		if(bo) { return li[l++%li.Count]; }
		li.Add(Console.ReadLine());
		return li[li.Count-1];
	}
	public void Again() { bo=true; }
}
public class Scs:Sc {
	private StreamReader sr;
	private string path;
	public Scs(string path) { sr=new StreamReader(this.path=path); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected override string Rl() { return sr.ReadLine(); }
	public void Close() { sr.Close(); }
	public void Reset() { sr=new StreamReader(path); }
}
public class Sc2:Sc {
	private string[] sps = new string[] { " ","　","\t" };
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected override string[] Sp(string st) { return st.Split(sps,StringSplitOptions.RemoveEmptyEntries); }
	public override int I { get { return int.Parse(Sp(Rl())[0]); } }
	public override long L { get { return long.Parse(Sp(Rl())[0]); } }
	public override double D { get { return double.Parse(Sp(Rl())[0]); } }
	public override string S { get { return Sp(Rl())[0]; } }
}
public class Scs2:Sc2 {
	private StreamReader sr;
	public Scs2(string t) { sr=new StreamReader(t); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected override string Rl() { return sr.ReadLine(); }
	public void Close() { sr.Close(); }
}
public class Sct:Sc {
	private List<string> li = new List<string>();
	private int l = 0;
	public void Add(int s) { li.Add(s.ToString()); }
	public void Add(long s) { li.Add(s.ToString()); }
	public void Add(double s) { li.Add(s.ToString()); }
	public void Add(string s) { li.Add(s.ToString()); }
	public void Add(object s) { li.Add(s.ToString()); }
	public void Add(int[] s) { li.Add(string.Join(" ",s)); }
	public void Add(long[] s) { li.Add(string.Join(" ",s)); }
	public void Add(double[] s) { li.Add(string.Join(" ",s)); }
	public void Add(string[] s) { li.Add(string.Join(" ",s)); }
	public void Add(params object[] s) { li.Add(string.Join(" ",s)); }
	protected override string Rl() { return li[l++]; }
	public void Clear() { li.Clear(); l=0; }
	public void Again() { l=0; }
	public void Pf() { Console.WriteLine(string.Join("\n",li)); }
}
0