codeforces E - Anya and Cubes 分块处理 暴力搜索

说的是给了n个立方体，立方体从1标号到n，每个立方体上有一个数字， 你有 k 个机会 使得其中 k个数位他们自己的阶乘，（自然使用可以少于k次机会，每个立方体最多被使用1次） ，那么求出你从这n个立方体重选出任意个立方体使得 他们的和为S

n<25

可以知道直接使用n去枚举自然受不了， 我们将n个数字分为两部分来算，前面n/2个数字 我们枚举他们使用j次可以得到的数，然后后面的n-n/2个数再次使用这个方法，直接在dfs枚举的时候进行判断S-s 在前一个钟是否出现过，出现过就加起来。 分块处理

 #include <iostream>

 #include <algorithm>

 #include <string.h>

 #include <map>

 #include<cstdio>

 using namespace std;

 typedef long long LL;

 map<LL,int>mp[];

 LL A[];

 LL dp[];

 LL time[];

 int n,K;

 LL S,ans;

 void dfs(int p, int k, LL s){

     if(p==n/){

          mp[k][s]++;

     }else{

         dfs(p+,k,s);

         if(s+A[p]<=S)dfs(p+,k,s+A[p]);

         if(k+<=K && A[p]<= &&  s+dp[A[p]] <=S ) dfs(p+,k+,s+dp[A[p]]);

     }

 }

 void dfs1(int p, int k, LL s){

     if(p==n){

          for(int i =; i+k<=K; i++)

             if(mp[i].count(S-s)>) ans+=mp[i][S-s];

     }else{

          dfs1(p+,k,s);

          if(s+A[p]<=S) dfs1(p+,k,s+A[p]);

          if(k+<=K && A[p]<= && s+dp[A[p]]<=S) dfs1(p+,k+,s+dp[A[p]]);

     }

 }

 int main()

 {

    dp[]=;

    for(LL i=; i<=; i++) dp[i]=dp[i-]*i;

    ans=;

    scanf("%d%d%I64d",&n,&K,&S);

    for(int i=; i<n; i++)

       scanf("%I64d",&A[i]);

    dfs(,,);

    dfs1(n/,,);

    printf("%I64d\n",ans);

     return ;

 }