CF525E Anya and Cubes（meet in the middle）

题面

给你\(n\)个数,\(n\le 26\)初始序列为\(a_i,0\le a_i\le 10^9\)

你有\(k\)个\(!\),每个\(!\)可以使序列中的一个数变成\(a_i!\)

例如\(5!=120\)

求:选出任意个数使他们和的等于S的方案数

题解

\(meet-in-the-middle\)

简单来说就是前半部分和后半部分分别爆搜

用个\(map\)啥的存一下前半部分的结果，后半部分的对应加上贡献就是了

ps：话说\(unordered\_map\)跑得比\(map\)快好多啊……但问题是我本地的dev上连编译都过不去……

//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
const int N=35;
ll fac[N],res,S;int n,k,a[N];unordered_map<ll,ll>mp[N];
void dfs1(int pos,int end,int t,ll s){
    if(pos>end)return ++mp[t][s],void();
    dfs1(pos+1,end,t,s);
    if(s+a[pos]<S+1)dfs1(pos+1,end,t,s+a[pos]);
    if(t<k&&a[pos]<21&&s+fac[a[pos]]<S+1)dfs1(pos+1,end,t+1,s+fac[a[pos]]);
}
void dfs2(int pos,int end,int t,ll s){
    if(pos>end){
        fp(i,0,k-t)res+=mp[i][S-s];
        return;
    }
    dfs2(pos+1,end,t,s);
    if(s+a[pos]<S+1)dfs2(pos+1,end,t,s+a[pos]);
    if(t<k&&a[pos]<21&&s+fac[a[pos]]<S+1)dfs2(pos+1,end,t+1,s+fac[a[pos]]);
}
int main(){
//  freopen("testdata.in","r",stdin);
    scanf("%d%d%lld",&n,&k,&S);
    fac[0]=1;fp(i,1,20)fac[i]=fac[i-1]*i;
    fp(i,1,n)scanf("%d",&a[i]);
    dfs1(1,(n+1)>>1,0,0),dfs2(((n+1)>>1)+1,n,0,0);
    printf("%lld\n",res);
    return 0;
}

CF525E Anya and Cubes（meet in the middle）

原文：https://www.cnblogs.com/bztMinamoto/p/10446575.html