Submission #40569949

Source Code Expand

P,H,W,K = 998244353,*gets.split.map(&:to_i)
Ck = lambda{|x,p,r|
	num,dnm = [1,1],[1,1]
	2.upto(x){|n|
		num << num[-1]*n%p
		dnm << p - dnm[p%n]*(p/n)%p # 謎
	}
	1.upto(dnm.size-1){|n|
		dnm[n] = dnm[n-1]*dnm[n]%p # 謎
	}
	next (0..x).map{|n|
		n<r ? 0 : num[n]*dnm[r]*dnm[n-r]%p
	}
}.call H*W,P,K
p (1..H).sum{|h|
	(1..W).sum{|w|
		z = Ck[h*w]
		z -= 2*(Ck[(h-1)*w]+Ck[h*(w-1)])
		z += Ck[(h-2)*w] if 1<h
		z += Ck[h*(w-2)] if 1<w
		z += 4*Ck[(h-1)*(w-1)]
		z -= 2*Ck[(h-2)*(w-1)] if 1<h
		z -= 2*Ck[(h-1)*(w-2)] if 1<w
		z += Ck[(h-2)*(w-2)] if 1<h && 1<w
		next h*w*(H-h+1)*(W-w+1)*z%P
	}
}*Ck[H*W].pow(P-2,P)%P

Submission Info

Submission Time
Task F - Minimum Bounding Box 2
User ds14050
Language Ruby (2.7.1)
Score 500
Code Size 644 Byte
Status AC
Exec Time 1081 ms
Memory 37824 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 20
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 57 ms 14196 KiB
00_sample_02.txt AC 53 ms 14140 KiB
00_sample_03.txt AC 98 ms 15736 KiB
01_test_01.txt AC 60 ms 14220 KiB
01_test_02.txt AC 57 ms 14256 KiB
01_test_03.txt AC 706 ms 37636 KiB
01_test_04.txt AC 1081 ms 37760 KiB
01_test_05.txt AC 1072 ms 37664 KiB
01_test_06.txt AC 1079 ms 37824 KiB
01_test_07.txt AC 845 ms 36180 KiB
01_test_08.txt AC 847 ms 33952 KiB
01_test_09.txt AC 631 ms 34900 KiB
01_test_10.txt AC 764 ms 37192 KiB
01_test_11.txt AC 705 ms 35984 KiB
01_test_12.txt AC 415 ms 23672 KiB
01_test_13.txt AC 716 ms 30196 KiB
01_test_14.txt AC 363 ms 22608 KiB
01_test_15.txt AC 518 ms 25772 KiB
01_test_16.txt AC 267 ms 20204 KiB
01_test_17.txt AC 470 ms 25076 KiB