CFR 525 E. Anya and Cubes ( Search )

Problem - E - Codeforces

題意：
給 N 個數字的數列 A[]。你可以選至多 K 個數字，將它們變成自己的階乘，這個操作對同一個元素只能使用一次。問有幾種方法可以得到一個子集合，其總和恰為 S。兩種方法相同若且唯若集合相同且施加的操作相同。

資料規模：
The first line of the input contains three space-separated integers n, k and S (1 ≤ n ≤ 25, 0 ≤ k ≤ n, 1 ≤ S ≤ 1e16) — the number of cubes and the number of stickers that Anya has, and the sum that she needs to get.
The second line contains n positive integers ai (1 ≤ ai ≤ 1e9) — the numbers, written on the cubes. The cubes in the input are described in the order from left to right, starting from the first one.

解法：
如果直接枚舉階乘怎麼放，會是 3^25 級別。考慮拆半列舉，一邊只有 3^13，可以負荷。用 map 存狀態對應方案數。
python 的 dict 貌似不支援給未定義的 key 賦值，但 collections.defaultdict 幾乎跟 C++ 的 map 一樣可用。
pypy3 真快。

時間 / 空間複雜度：
O( 3^(N/2) lg 3^(N/2 ) / O( 3^(N/2) )

fact = [ 1 ]
for i in range( 1, 20, 1 ):
  fact.append( fact[ i - 1 ] * i )

from collections import defaultdict

N, K, S = map( int, input().split() )
A = list( map( int, input().split() ) )

ldp = [ [ defaultdict( int ) for i in range( K + 1 ) ] for j in range( 2 ) ]
ldp[ 0 ][ 0 ][ 0 ] = 1
for i in range( N // 2 ):
  for j in range( K + 1 ):
    ldp[ ~ i & 1 ][ j ].clear()
  for j in range( K + 1 ):
    for key in ldp[ i & 1 ][ j ]:
      ldp[ ~ i & 1 ][ j ][ key ] += ldp[ i & 1 ][ j ][ key ] # toranai
      ldp[ ~ i & 1 ][ j ][ key + A[ i ] ] += ldp[ i & 1 ][ j ][ key ] # toru
      if j + 1 <= K and A[ i ] <= 18:
        ldp[ ~ i & 1 ][ j + 1 ][ key + fact[ A[ i ] ] ] += ldp[ i & 1 ][ j ][ key ] # kaijyou totte toru

rdp = [ [ defaultdict( int ) for i in range( K + 1 ) ] for j in range( 2 ) ]
rdp[ 0 ][ 0 ][ 0 ] = 1
for i in range( N - N // 2 ):
  for j in range( K + 1 ):
    rdp[ ~ i & 1 ][ j ].clear()
  for j in range( K + 1 ):
    for key in rdp[ i & 1 ][ j ]:
      rdp[ ~ i & 1 ][ j ][ key ] += rdp[ i & 1 ][ j ][ key ]
      rdp[ ~ i & 1 ][ j ][ key + A[ N // 2 + i ] ] += rdp[ i & 1 ][ j ][ key ]
      if j + 1 <= K and A[ N // 2 + i ] <= 18:
        rdp[ ~ i & 1 ][ j + 1 ][ key + fact[ A[ N // 2 + i ] ] ] += rdp[ i & 1 ][ j ][ key ]

ans = 0
for i in range( K + 1 ):
  for key in ldp[ N // 2 & 1 ][ i ]:
    for j in range( 0, K - i + 1, 1 ):
      ans += ldp[ N // 2 & 1 ][ i ][ key ] * rdp[ N - N // 2 & 1 ][ j ][ S - key ]

print( ans )