提出 #42262239

ソースコード 拡げる

P = 998244353
N,M = gets.split.map(&:to_i)
S = M.times.map{ gets.chomp.tr('ab','01') }.group_by(&:size)
N5 = [N,5].min

B06 = [b0 = {}]
1.upto(6){|k|
	B06<<b1 = {}
	b0.each_key{|b|
		b1[b] =
		b1[b<<1] =
		b1[b<<1|1] =
		b1[1<<k-1|b] = 0
	}
	(S[k]||[]).each{|b|
		b1[b.to_i(2)] = 0
	}
	b0 = b1
}
B6 = b0
A5 = [*0...1<<N5]-B06[N5].keys
as = [1]*A5.size
xs = A5.map{ A5.map{ 0 } }
A5.each_with_index{|a5,i|
	a6 = a5<<1
	a5 = a6&(1<<N5)-1
	j = A5.index a5
	xs[i][j] = 1 if ! B6[a6] && j
	a6 |= 1
	a5 |= 1
	j = A5.index a5
	xs[i][j] = 1 if ! B6[a6] && j
}
x = N-N5
while 0<x
	as = xs.map{|c| c.zip(as).sum{|x,a| x*a }%P } if 0<x&1
	ys = xs.transpose
	xs = xs.map{|c| ys.map{|r| r.zip(c).sum{ _1*_2 }%P } }
	x >>= 1
end

p as.sum%P

提出情報

提出日時
問題 G - Banned Substrings
ユーザ ds14050
言語 Ruby (2.7.1)
得点 550
コード長 769 Byte
結果 AC
実行時間 257 ms
メモリ 14500 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 550 / 550
結果
AC × 3
AC × 42
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 02_max_13.txt, 02_max_14.txt, 02_max_15.txt, 02_max_16.txt, 02_max_17.txt, 02_max_18.txt, 02_max_19.txt, 02_max_20.txt, 02_max_21.txt, 02_max_22.txt, 03_handmade_23.txt, 03_handmade_24.txt, 03_handmade_25.txt, 03_handmade_26.txt, 03_handmade_27.txt, 03_handmade_28.txt, 03_handmade_29.txt, 03_handmade_30.txt, 03_handmade_31.txt, 04_small_32.txt, 04_small_33.txt, 04_small_34.txt, 04_small_35.txt, 04_small_36.txt, 04_small_37.txt, 04_small_38.txt, 04_small_39.txt, 04_small_40.txt, 04_small_41.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 59 ms 14088 KiB
00_sample_01.txt AC 59 ms 14164 KiB
00_sample_02.txt AC 154 ms 14336 KiB
01_random_03.txt AC 90 ms 14104 KiB
01_random_04.txt AC 76 ms 14196 KiB
01_random_05.txt AC 164 ms 14212 KiB
01_random_06.txt AC 58 ms 14104 KiB
01_random_07.txt AC 60 ms 14084 KiB
01_random_08.txt AC 125 ms 14396 KiB
01_random_09.txt AC 59 ms 14060 KiB
01_random_10.txt AC 63 ms 14236 KiB
01_random_11.txt AC 57 ms 14152 KiB
01_random_12.txt AC 61 ms 14052 KiB
02_max_13.txt AC 256 ms 14272 KiB
02_max_14.txt AC 256 ms 14296 KiB
02_max_15.txt AC 256 ms 14500 KiB
02_max_16.txt AC 254 ms 14200 KiB
02_max_17.txt AC 255 ms 14412 KiB
02_max_18.txt AC 255 ms 14476 KiB
02_max_19.txt AC 253 ms 14228 KiB
02_max_20.txt AC 255 ms 14232 KiB
02_max_21.txt AC 257 ms 14424 KiB
02_max_22.txt AC 256 ms 14356 KiB
03_handmade_23.txt AC 62 ms 14140 KiB
03_handmade_24.txt AC 60 ms 14076 KiB
03_handmade_25.txt AC 236 ms 14220 KiB
03_handmade_26.txt AC 251 ms 14344 KiB
03_handmade_27.txt AC 57 ms 14132 KiB
03_handmade_28.txt AC 63 ms 14080 KiB
03_handmade_29.txt AC 56 ms 14000 KiB
03_handmade_30.txt AC 56 ms 14160 KiB
03_handmade_31.txt AC 54 ms 13972 KiB
04_small_32.txt AC 57 ms 14312 KiB
04_small_33.txt AC 56 ms 14160 KiB
04_small_34.txt AC 58 ms 14148 KiB
04_small_35.txt AC 57 ms 14144 KiB
04_small_36.txt AC 59 ms 14000 KiB
04_small_37.txt AC 59 ms 14188 KiB
04_small_38.txt AC 57 ms 14044 KiB
04_small_39.txt AC 59 ms 14224 KiB
04_small_40.txt AC 59 ms 14168 KiB
04_small_41.txt AC 57 ms 14260 KiB