Submission #26862342

Source Code Expand

N,S,*A = $<.read.split.map(&:to_i)
P = 998244353
C = 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
	}
}.call N,P
P2 = N.times.inject([1]){|s,| s<<s[-1]*2%P }
S2 = S+2

A.sort_by!(&:-@)
A.shift while A[0]&.>S
p (A.tally.inject([1]){|s0,(a,n)|
	s1,a0 = [0]*(S2-a),-s0.size

	r1,a1 = n+1,-a
	until 0 > r1 -= 1 or S < a1 += a
		n1 = C[n,r1]*P2[r1]%P
		s0[a0,~a1-a0].each.with_index(a0+a1){|n0,a|
			s1[a] += n0*n1%P
		} if a0+a1 < -1
		s1[a1<1?-1:a1-S2] += s0[-1]*n1%P
	end

	next s1
}[-2]||0)*2.pow(N-A.size,P)%P

Submission Info

Submission Time
Task F - Knapsack for All Subsets
User ds14050
Language Ruby (2.7.1)
Score 600
Code Size 717 Byte
Status AC
Exec Time 679 ms
Memory 21868 KiB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 27
Set Name Test Cases
sample sample01, sample02, sample03
All 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, sample01, sample02, sample03
Case Name Status Exec Time Memory
11 AC 65 ms 14096 KiB
12 AC 61 ms 14240 KiB
13 AC 63 ms 14292 KiB
14 AC 60 ms 14116 KiB
15 AC 59 ms 14228 KiB
21 AC 61 ms 14404 KiB
22 AC 269 ms 21868 KiB
23 AC 174 ms 19576 KiB
24 AC 176 ms 18304 KiB
25 AC 82 ms 15420 KiB
31 AC 209 ms 14468 KiB
32 AC 328 ms 14360 KiB
33 AC 296 ms 14340 KiB
34 AC 298 ms 14372 KiB
35 AC 305 ms 14328 KiB
41 AC 673 ms 20240 KiB
42 AC 673 ms 20128 KiB
43 AC 663 ms 20648 KiB
44 AC 673 ms 20060 KiB
45 AC 679 ms 20120 KiB
51 AC 60 ms 14100 KiB
52 AC 58 ms 14012 KiB
53 AC 63 ms 14556 KiB
54 AC 59 ms 14312 KiB
sample01 AC 59 ms 14108 KiB
sample02 AC 59 ms 14188 KiB
sample03 AC 57 ms 14148 KiB