#976986 (C#) No.569 3 x N グリッドのパスの数

提出ソース

結果

問題	No.569 3 x N グリッドのパスの数
ユーザー	fgwiebfaoish
提出日時	2024-04-23 23:02:04
言語	C# (.NET 8.0.203)
結果	AC
実行時間	130 ms / 2,000 ms
コード長	14,954 bytes
コンパイル時間	8,608 ms
コンパイル使用メモリ	170,964 KB
実行使用メモリ	201,096 KB
最終ジャッジ日時	2024-11-06 05:19:44
合計ジャッジ時間	16,892 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	76 ms 36,480 KB
testcase_01	AC	73 ms 36,480 KB
testcase_02	AC	77 ms 36,708 KB
testcase_03	AC	76 ms 36,608 KB
testcase_04	AC	75 ms 36,736 KB
testcase_05	AC	76 ms 36,608 KB
testcase_06	AC	78 ms 36,608 KB
testcase_07	AC	78 ms 36,608 KB
testcase_08	AC	78 ms 36,608 KB
testcase_09	AC	81 ms 36,608 KB
testcase_10	AC	79 ms 36,716 KB
testcase_11	AC	76 ms 36,600 KB
testcase_12	AC	77 ms 36,732 KB
testcase_13	AC	78 ms 36,608 KB
testcase_14	AC	77 ms 36,608 KB
testcase_15	AC	78 ms 36,608 KB
testcase_16	AC	79 ms 36,480 KB
testcase_17	AC	79 ms 36,708 KB
testcase_18	AC	81 ms 36,992 KB
testcase_19	AC	83 ms 36,608 KB
testcase_20	AC	106 ms 37,504 KB
testcase_21	AC	107 ms 37,248 KB
testcase_22	AC	105 ms 37,248 KB
testcase_23	AC	106 ms 37,120 KB
testcase_24	AC	106 ms 37,248 KB
testcase_25	AC	106 ms 37,376 KB
testcase_26	AC	103 ms 37,120 KB
testcase_27	AC	101 ms 36,992 KB
testcase_28	AC	100 ms 36,992 KB
testcase_29	AC	101 ms 37,120 KB
testcase_30	AC	100 ms 37,376 KB
testcase_31	AC	101 ms 37,504 KB
testcase_32	AC	100 ms 37,248 KB
testcase_33	AC	100 ms 36,992 KB
testcase_34	AC	101 ms 37,248 KB
testcase_35	AC	102 ms 37,120 KB
testcase_36	AC	101 ms 37,376 KB
testcase_37	AC	101 ms 37,348 KB
testcase_38	AC	100 ms 37,120 KB
testcase_39	AC	102 ms 37,376 KB
testcase_40	AC	126 ms 37,760 KB
testcase_41	AC	126 ms 37,760 KB
testcase_42	AC	127 ms 38,144 KB
testcase_43	AC	127 ms 37,760 KB
testcase_44	AC	129 ms 37,760 KB
testcase_45	AC	125 ms 37,888 KB
testcase_46	AC	127 ms 37,888 KB
testcase_47	AC	126 ms 37,888 KB
testcase_48	AC	130 ms 37,888 KB
testcase_49	AC	129 ms 37,888 KB
testcase_50	AC	127 ms 37,884 KB
testcase_51	AC	126 ms 37,888 KB
testcase_52	AC	129 ms 37,888 KB
testcase_53	AC	130 ms 37,760 KB
testcase_54	AC	127 ms 37,888 KB
testcase_55	AC	128 ms 38,016 KB
testcase_56	AC	126 ms 38,016 KB
testcase_57	AC	126 ms 38,016 KB
testcase_58	AC	124 ms 37,760 KB
testcase_59	AC	123 ms 201,096 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (97 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

raw source code

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

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード