Submission #54414039

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 30 行目(オリジナルの 27 行目)だけ改変しました。
# https://atcoder.jp/contests/arc179/submissions/54319004
$debug = !ARGV[0].nil?
M, N = STDIN.gets.chomp.split.map(&:to_i)
XS = STDIN.gets.chomp.split.map(&:to_i)
R = 998244353
rxs = Array.new(M, 0)
XS.each.with_index do |x, i|
  rxs[x - 1] += (1 << i)
end
$n_2_n2_r = Array.new(1 << M) { [] }
(1 << M).times do |n|
  n.digits(2).each.with_index do |d, i|
    next if d == 0
    n2 = n & ~(1 << i) | rxs[i]
    $n_2_n2_r[n2] << n
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

# 30 行目(オリジナルの 27 行目)だけ改変しました。
# https://atcoder.jp/contests/arc179/submissions/54319004

$debug = !ARGV[0].nil?

M, N = STDIN.gets.chomp.split.map(&:to_i)
XS = STDIN.gets.chomp.split.map(&:to_i)

R = 998244353

rxs = Array.new(M, 0)
XS.each.with_index do |x, i|
  rxs[x - 1] += (1 << i)
end

$n_2_n2_r = Array.new(1 << M) { [] }
(1 << M).times do |n|
  n.digits(2).each.with_index do |d, i|
    next if d == 0
    n2 = n & ~(1 << i) | rxs[i]
    $n_2_n2_r[n2] << n
  end
end

def count
  dp = Array.new(1 << M, 0)
  dp[(1 << M) - 1] = 1 # first status

  N.times do |i|
    dp = $n_2_n2_r.map { |ns| dp.values_at(*ns).sum }
    if i % 8 == 0
      dp = dp.map { |d| d % R }
    end
  end

  dp.sum % R
end

puts count

Submission Info

Judge Result