题意：

一共有N个数字，我们可以最多使用K次魔法，一共有多少种方案使其和能够为S、

使用魔法的同时只能对一个数字使用，能够使其变成!ai，就是ai这个数的阶乘。

题解：

我们可以采用折半搜索的方法
就是处理前一半，把结果储存起来，再处理后一半，然后匹配前一半存储的结果。
放在本题上，我们记录前半区间的值和对应的k的使用情况，再记录后半区间的值，然后根据前半区间的情况看后半区间是否有对应情况
比如前半区间值为W，就看后半区间有几个S-W，因为要求值为S
当然W可以为0，也可以为S
这个方法也叫折半DFS
能降低复杂度

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
   return s*w;
}
ll p[30];
const int maxn=30;
struct node{
    int sum;
    int ksum;
}b[1200080];
int a[1200004];
int tot=0;
ll n,K,s;
map<ll,ll>mp[maxn];//用[i]次阶乘，和为[j]的方案数
void dfs(int cnt,int k,int sum,int end)
{
    //cnt为当前做选数的坐标 （cnt初始值为前边界） 
    //k表示所用魔法的数量
    //sum为当前所能表示的值
    //end表示后边界 
    if(sum>s||K<k)return ;

    if(cnt>end)
    {
        if(end==n/2)//左半区 
        {
            tot++;//左半区所能表达的数的数量 
            b[tot].ksum=k;
            b[tot].sum=sum;
        } 
        else if(end==n)//后半区 
        {
            mp[k][sum]++;//记录 后半区的值 
        }
        return ;
    }

    dfs(cnt+1,k,sum,end);//不选 
    dfs(cnt+1,k,sum+a[cnt],end);//选本身 
    if(a[cnt]<19)dfs(cnt+1,k+1,sum+p[a[cnt]],end);//选阶乘 
}
void init()
{
    p[1]=1;
    for(ll i=2;i<19;i++)p[i]=p[i-1]*i;
}
int main()
{

    cin>>n>>K>>s;
    for(int i=1;i<=n;i++)cin>>a[i];
    int mid=n/2;
    dfs(1,0,0,mid);
    dfs(mid+1,0,0,n);
    ll ans=0;
    for(int i=1;i<=tot;i++)
    {
        for(int k=0;k<=K-b[i].ksum;k++)
        {
            ans+=mp[k][s-b[i].sum];
        } 
    }
    cout<<ans;
    return 0;
}