# CFR 525 E. Anya and Cubes ( Search )

Problem - E - Codeforces

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.

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 )
```