提出 #36313584

ソースコード 拡げる

P,N,M = 998244353,*gets.split.map(&:to_i)
I = N-1
exit p 0 if M<I
ICI,C1,C3,FD = lambda{|x,p|
	fn = 1,1
	ir = 1,1
	fd = 1,1
	n = r = d = 1
	2.upto(x){|i|
		fn<<n = n*i%p
		ir<<r = p-ir[p%i]*(p/i)%p # 謎
		fd<<d = d*r%p
	}
	fn.shift I-1
	next fn[1]*fd[I-1]%P,lambda{|r|
		fd[r]*fd[I-r]%p
	},lambda{|r|
		fn[r]*fd[r]%p
	},fd
}.call (M-I)/3+I,P

A = FD[0..I/2].map.with_index{|fdr,r| fdr*FD[I-r]%P }
s,*S = 0
t,*T = 0
n = N+1
A.each{|c1|
	S<<s = (s+c1)%P
	T<<t = (t+c1*n-=1)%P
}
A.pop if I&1<1
while c1 = A.pop
	S<<s = (s+c1)%P
	T<<t = (t+c1*n-=1)%P
end

m = M-I+3
s = S[I]
t = T[I]
p ICI*(0..(M-I)/3).sum{|n3|
	m -= 3
	# n1: 0..[m,I].min
	# n0: m..[0,m-I].max
	if m<I
		s = S[m]
		t = T[m]
	end
	next C3[n3]*(t+s*(m-I))%P
}%P

提出情報

提出日時
問題 G - Count Sequences
ユーザ ds14050
言語 Ruby (2.7.1)
得点 600
コード長 773 Byte
結果 AC
実行時間 3938 ms
メモリ 434632 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 600 / 600
結果
AC × 2
AC × 49
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_smallNM_00.txt, 01_smallNM_01.txt, 01_smallNM_02.txt, 01_smallNM_03.txt, 01_smallNM_04.txt, 01_smallNM_05.txt, 01_smallNM_06.txt, 01_smallNM_07.txt, 01_smallNM_08.txt, 01_smallNM_09.txt, 01_smallNM_10.txt, 01_smallNM_11.txt, 02_smallN_00.txt, 02_smallN_01.txt, 02_smallN_02.txt, 02_smallN_03.txt, 02_smallN_04.txt, 02_smallN_05.txt, 02_smallN_06.txt, 03_rnd_00.txt, 03_rnd_01.txt, 03_rnd_02.txt, 03_rnd_03.txt, 03_rnd_04.txt, 03_rnd_05.txt, 03_rnd_06.txt, 03_rnd_07.txt, 04_max_00.txt, 04_max_01.txt, 04_max_02.txt, 04_max_03.txt, 04_max_04.txt, 04_max_05.txt, 04_max_06.txt, 04_max_07.txt, 04_max_08.txt, 04_max_09.txt, 04_max_10.txt, 04_max_11.txt, 04_max_12.txt, 04_max_13.txt, 04_max_14.txt, 04_max_15.txt, 04_max_16.txt, 04_max_17.txt, 04_max_18.txt, 04_max_19.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 56 ms 14196 KiB
00_sample_01.txt AC 1806 ms 117264 KiB
01_smallNM_00.txt AC 54 ms 14040 KiB
01_smallNM_01.txt AC 54 ms 14264 KiB
01_smallNM_02.txt AC 56 ms 14096 KiB
01_smallNM_03.txt AC 56 ms 14068 KiB
01_smallNM_04.txt AC 55 ms 14160 KiB
01_smallNM_05.txt AC 54 ms 14260 KiB
01_smallNM_06.txt AC 57 ms 14164 KiB
01_smallNM_07.txt AC 56 ms 13964 KiB
01_smallNM_08.txt AC 55 ms 14004 KiB
01_smallNM_09.txt AC 54 ms 14052 KiB
01_smallNM_10.txt AC 55 ms 14188 KiB
01_smallNM_11.txt AC 59 ms 14116 KiB
02_smallN_00.txt AC 1202 ms 92316 KiB
02_smallN_01.txt AC 1218 ms 104664 KiB
02_smallN_02.txt AC 1780 ms 104784 KiB
02_smallN_03.txt AC 1766 ms 104900 KiB
02_smallN_04.txt AC 1785 ms 104992 KiB
02_smallN_05.txt AC 1816 ms 116956 KiB
02_smallN_06.txt AC 1764 ms 117076 KiB
03_rnd_00.txt AC 56 ms 14164 KiB
03_rnd_01.txt AC 1184 ms 132288 KiB
03_rnd_02.txt AC 58 ms 14168 KiB
03_rnd_03.txt AC 2815 ms 278172 KiB
03_rnd_04.txt AC 55 ms 14132 KiB
03_rnd_05.txt AC 2352 ms 218112 KiB
03_rnd_06.txt AC 52 ms 13972 KiB
03_rnd_07.txt AC 1039 ms 119772 KiB
04_max_00.txt AC 3929 ms 434632 KiB
04_max_01.txt AC 2926 ms 266068 KiB
04_max_02.txt AC 2371 ms 210656 KiB
04_max_03.txt AC 2074 ms 144756 KiB
04_max_04.txt AC 1914 ms 130888 KiB
04_max_05.txt AC 3882 ms 434316 KiB
04_max_06.txt AC 55 ms 14124 KiB
04_max_07.txt AC 55 ms 14240 KiB
04_max_08.txt AC 3916 ms 434240 KiB
04_max_09.txt AC 3904 ms 434300 KiB
04_max_10.txt AC 3900 ms 434236 KiB
04_max_11.txt AC 56 ms 14252 KiB
04_max_12.txt AC 3914 ms 434256 KiB
04_max_13.txt AC 3893 ms 434300 KiB
04_max_14.txt AC 3909 ms 434448 KiB
04_max_15.txt AC 3922 ms 434192 KiB
04_max_16.txt AC 3896 ms 434332 KiB
04_max_17.txt AC 3893 ms 434264 KiB
04_max_18.txt AC 3905 ms 434288 KiB
04_max_19.txt AC 3938 ms 434084 KiB