提出 #48681702

ソースコード 拡げる

P = 998244353
N = gets.to_i
C,Cn,Cr = lambda{|x,p|
	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 lambda{|n,r|
		num[n]*dnm[r]*dnm[n-r]%p
	},num,dnm
}.call N,P
D2 = 2.pow P-2,P

D = [1]
one = D2
1.upto(N-1){|n|
	one = one*D2%P
	D<<(1-one).pow(P-2,P)*one%P*Cn[n]*(0...n).sum{|r|
		Cr[r]*Cr[n-r]%P*D[r]
	}%P
}

one = 2
puts (0...N).map{|n|
	one = one*D2%P
	one*Cn[n]%P*(0..n).sum{|r|
		Cr[r]*Cr[n-r]%P*D[N-1-n+r]
	}%P
}*' '

提出情報

提出日時
問題 F - Bomb Game 2
ユーザ ds14050
言語 Ruby (ruby 3.2.2)
得点 550
コード長 574 Byte
結果 AC
実行時間 619 ms
メモリ 17756 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 550 / 550
結果
AC × 2
AC × 25
セット名 テストケース
Sample 00_sample_01.txt, 00_sample_02.txt
All 00_sample_01.txt, 00_sample_02.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, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt
ケース名 結果 実行時間 メモリ
00_sample_01.txt AC 115 ms 17108 KiB
00_sample_02.txt AC 46 ms 17148 KiB
01_test_01.txt AC 47 ms 17136 KiB
01_test_02.txt AC 48 ms 16992 KiB
01_test_03.txt AC 613 ms 17700 KiB
01_test_04.txt AC 611 ms 17604 KiB
01_test_05.txt AC 207 ms 17684 KiB
01_test_06.txt AC 454 ms 17720 KiB
01_test_07.txt AC 315 ms 17552 KiB
01_test_08.txt AC 366 ms 17652 KiB
01_test_09.txt AC 469 ms 17672 KiB
01_test_10.txt AC 196 ms 17456 KiB
01_test_11.txt AC 619 ms 17664 KiB
01_test_12.txt AC 600 ms 17432 KiB
01_test_13.txt AC 588 ms 17628 KiB
01_test_14.txt AC 599 ms 17464 KiB
01_test_15.txt AC 593 ms 17684 KiB
01_test_16.txt AC 56 ms 17524 KiB
01_test_17.txt AC 52 ms 17188 KiB
01_test_18.txt AC 71 ms 17616 KiB
01_test_19.txt AC 101 ms 17412 KiB
01_test_20.txt AC 588 ms 17592 KiB
01_test_21.txt AC 451 ms 17756 KiB
01_test_22.txt AC 117 ms 17608 KiB
01_test_23.txt AC 111 ms 17464 KiB