#977657 (C#) No.541 3 x N グリッド上のサイクルの個数

提出ソース

結果

問題	No.541 3 x N グリッド上のサイクルの個数
ユーザー	fgwiebfaoish
提出日時	2024-04-27 16:25:24
言語	C# (.NET 8.0.203)
結果	WA
実行時間	-
コード長	15,946 bytes
コンパイル時間	19,108 ms
コンパイル使用メモリ	168,224 KB
実行使用メモリ	200,504 KB
最終ジャッジ日時	2024-11-15 20:06:22
合計ジャッジ時間	26,474 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
testcase_51	WA	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	WA	-
testcase_55	WA	-
testcase_56	WA	-
testcase_57	WA	-
testcase_58	WA	-
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-

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

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (99 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 h = sc.L;
		var ft = new Frontier(h+1,4,true);
		ft.Ce1();
		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;
	private bool isve;
	public long[][] ba;
	public Frontier(long h,int w,bool isve = false) {
		this.h=h;
		Dt.w=this.w=w;
		this.isve=isve;
		if(isve) gm=w;
		else gm=(w+1)>>1;
		Dt.gn=gn=(int)Ceiling(Log(gm,2));
	}
	public long Dp() {
		var dp = Enumerable.Repeat(0L,li.Count).ToArray();
		dp[0]=1;
		var lar = li.Select((v,i) => new { v,i }).First(x => x.v.n==(1<<(w-1))).i;
		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 = 0;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[1];
		return ans;
	}
	public long Mp() {
		var dp = Enumerable.Repeat(0L,li.Count).ToArray();
		dp[2]=1;
		var lar = li.Select((v,i) => new { v,i }).First(x => x.v.n==(1<<(w-1))).i;
		var mp = Mp2(dp,ba,h);
		return mp[lar];
	}
	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[k][j]*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];
			if(j==1) { continue; }
			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&&k!=1&&bb==0) { continue; }
				if(j==0&&k==1) { 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;
			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];
			ba[j][j]=1;
			if(j==1) { continue; }
			for(int k = 1;k<li.Count;k++) {
				for(int im = 0;im<mm;im++) {
					if(li[j].n==0&&li[k].n==0) { continue; }
					if(j==k) { continue; }
					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; }
					}
					var eds = 0;
					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) { eds|=1<<uf.Root(li[k].c+i); }
					}
					if(Pc(eds)>1||(eds!=0&&li[k].n!=0)) { 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; }
						}
					}
					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));
					if(i==0) { li.Add(new Dt(i,p,g,c)); }
				}
				else if(((i>>a)&1)==0) Fu(a+1,p,g,c);
				else if(!isve&&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,0);
			void Fu(int a,long p,int g,int c) {
				if(a==w) {
					li.Add(new Dt(i,p,g,c));
					if(i==0) { 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(!isve&&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 Ce3() {
		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));
					if(i==0) { li.Add(new Dt(i,p,1<<gn,c)); }
				}
				else if(((i>>a)&1)==0) Fu(a+1,p,c);
				else if(!isve&&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); }
				}
			}
		}
	}
	[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 bits) {
		bits-=(bits>>1)&0x55555555;
		bits=(bits&0x33333333)+((bits>>2)&0x33333333);
		return ((bits+(bits>>4)&0xF0F0F0F)*0x1010101)>>24;
	}
	static int Pc(long bits) {
		bits-=(bits>>1)&0x5555555555555555;
		bits=(bits&0x3333333333333333)+(bits>>2&0x3333333333333333);
		return (int)(((bits+(bits>>4))&0xf0f0f0f0f0f0f0f)*0x101010101010101>>56);
	}
	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 override string ToString() {
			var ca = new char[w];
			for(int i = 0;i<w;i++) {
				if(!Isu(i)) ca[w-i-1]='-';
				else ca[w-i-1]=(char)(Geg(i)+'0');
			}
			return string.Format("[{0:d4} {1} {2} {3} {4}]",n,Binary(n,w),c,string.Join("",ca),g,Binary(b,w*gn));
		}
		public string Binary(long a,int b) {
			string s = Convert.ToString(a,2);
			return (b>s.Length ? new string('0',b-s.Length) : "")+s;
		}
	}
}
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

結果

テストケース

コンパイルメッセージ

ソースコード