Description：

求长为 $n$ ，由非负整数构成的，每个数都不超过 $l$ 的，存在一个子序列和为 $k$ 的序列的方案数。

$1\le n,k \le 20,1\le l \le 10^9$

Solution：

看到 $k​$ 这么小可以状压 $DP​$ ，设 $f[i][S]​$ 表示到了 $i​$ ，可以加和表示出的 $\le k​$ 的数的集合为 $S​$ 的方案数，把所有非负整数分为两类，小于等于 $k​$ 的和大于 $k​$ 小于等于 $l​$ 的，对于大的，一定不会在最终和为 $k​$ 的子序列中出现，所以 $f[i][S]+=(l-k)\times f[i-1][S]​$ ，对于小的，转移就是 $f[i][(S\text{ or }(S<<j))\text{ and }tot]+=f[i][S]​$ 。最后把所有有 $k​$ 的状态加起来即可。

复杂度 $T(20)\times n(20)\times 2^{k}(1048576)\times \min(k,l)(20)\approx 8.4\times 10^8$ ，然而跑过了。

Code：