CF525E Anya and Cubes

@Pelom  October 24, 2019

题意

给你$n$个数,可以使用$k$次操作,每次操作可以使序列中的一个数$a_i$变为$a_i!$,求选出任意个数使他们和的等于$S$的方案数

数据范围:$1 \le n \le 25,0 \le k \le n,1 \le s \le 10^{16}$

题解

折半搜索
注意到$s \le 10^{16}$,因此只有$\le 19$的$a_i$需要考虑阶乘
另外,由于选择状态过多,难以记录;所以记录选择的阶乘的数量和总和

代码:

#include<iostream>
#include<cstdio>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N=25+5;
int n,k,tot;
LL s,ans;
int a[N];
LL fac[N];
unordered_map<LL,int> M[N];
void dfs1(int u,LL sum,int stt){
    if(sum>s || stt>k)
        return ;
    if(u>=tot){
        M[stt][sum]++;
        return ;
    }
    dfs1(u+1,sum,stt);
    dfs1(u+1,sum+a[u],stt);
    if(a[u]<=19)
        dfs1(u+1,sum+fac[a[u]],stt+1);
}
void dfs2(int u,LL sum,int stt){
    if(sum>s || stt>k)
        return ;
    if(u>=n){
        for(int i=0;i<=k-stt;i++)
            ans+=M[i][s-sum];
        return ;
    }
    dfs2(u+1,sum,stt);
    dfs2(u+1,sum+a[u],stt);
    if(a[u]<=19)
        dfs2(u+1,sum+fac[a[u]],stt+1);
}
int main(){
    fac[0]=1;
    for(int i=1;i<=19;i++)
        fac[i]=fac[i-1]*i;
    scanf("%d%d%lld",&n,&k,&s);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    tot=n>>1;
    dfs1(0,0,0);
    dfs2(tot,0,0);
    printf("%lld",ans);
    return 0;
}

添加新评论