部分集合の和の数え上げ(mod K)
問題
長さ$ Nの整数列$ A_1, A_2, \ldots, A_Nが与えられる。
この部分列のうち、和を$ Kで割ったあまりが$ Xになるものの個数を求めよ。
入力
整数$ N, K, X
長さ$ Nの数列$ A_i
計算量
$ O(NK)
コード1
$ dp \lbrack i \rbrack \lbrack j \rbrack =先頭から$ i個見たとき、和が$ jになる部分集合の個数
code:ruby
N, K, X = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
dp = Array.new(N + 1) { Array.new(K, 0) }
(0 ... N).each do |i|
(0 ... K).each do |j|
end
end
コード2
$ dp \lbrack i \rbrack =和が$ iになる部分集合の個数
code:ruby
N, K, X = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
dp = Array.new(K, 0)
A.each do |x|
K.times do |y|
end
end