CF525E Anya and Cubes

题意

题解

每个数有 $3$ 种状态，直接搜索 $O(3^{26})$ 会爆，但折半搜索的 $O(2\times 3^{13})$ 就可以。

注意到第一次搜索需要保存两个值 $cnt$ 和 $sum$ ，表示用阶乘的次数以及当前的数。可以用 unordered map 来维护，把第一个值开在外面。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

ll n,k,s,ans,a[30],fac[20];
unordered_map <ll,ll> mp[30];

void dfs1(ll x,ll sum,ll cnt)
{
    if (sum>s || cnt>k) return;
    if (x==n/2+1) return (void)mp[cnt][sum]++;
    dfs1(x+1,sum,cnt);
    dfs1(x+1,sum+a[x],cnt);
    if (a[x]<=19) dfs1(x+1,sum+fac[a[x]],cnt+1);
}

void dfs2(ll x,ll sum,ll cnt)
{
    if (sum>s || cnt>k) return;
    if (x==n+1)
    {
        for (ll i=0;i<=k-cnt;i++) ans+=mp[i][s-sum];
        return;
    }
    dfs2(x+1,sum,cnt);
    dfs2(x+1,sum+a[x],cnt);
    if (a[x]<=19) dfs2(x+1,sum+fac[a[x]],cnt+1); //20!>S
}

signed main()
{
    fac[0]=1;
    for (ll i=1;i<=19;i++) fac[i]=fac[i-1]*i;
    n=read(); k=read(); s=read();
    for (ll i=1;i<=n;i++) a[i]=read();
    dfs1(1,0,0);
    dfs2(n/2+1,0,0);
    return !printf("%lld",ans);
}