[CF 525E] Anya and Cubes

作法：

蠻顯然是切一半的題目。對兩半都枚舉「要拿哪些方塊，其中哪些要加驚嘆號」，把左半部的「加了 i 個驚嘆號後可以得到的所有數」都丟進一個 map 裡面，這樣在當枚舉到右半部的一個子集時，假設這個數為 s ，並且用了 t 個驚嘆號，那麼就可以把「左半部用了 <= k - t 個驚嘆號且湊出總和為 sum - s 的方法數」加到答案中。而因為能加上驚嘆號的數不能太大，算一下可以知道頂多會用到 18 ! ，因此在枚舉哪個子集要當階乘子集的時候只要考慮那些 <= 18 的數就可以了。

但這樣傳上去會 TLE ，因為在右半部找到新的一個數時，會用 for 迴圈跑第 0 ~ k - t 個 map 一次，這樣就導致 TLE 了，解決方法是把這個部份改成用 BIT 來寫，並且要注意到 BIT 必須使用 1 - base 就可以了。

======================================================

後來發現，其實可以不用改成BIT，只要在分配的時候把左邊分 n/2 + 1 個就可以了，因為慢的部份主要是右半部，所以當 n 是奇數的時候，分給左邊比右邊還多就可以加速很多了。

code :

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) (x&-x)
using namespace std;
const int maxn=25+3 ; /// 19! > 10^16
 
LL fac[19] ;
map<LL,int> mp[maxn] ;
int k,fac_s ;
LL ans=0LL , sum ;
LL all[1<<(maxn/2)],all2[1<<(maxn/2)] ;
 
void solve(const vector<int> &v,int type)
{
    int n=v.size() ;
    fac_s=0 ;
    for(int i=0;i<n;i++) if(v[i]<19)
        fac_s |= (1<<i) ;
 
    memset(all,0,sizeof(all)) ;
    memset(all2,0,sizeof(all2)) ;
    for(int i=0;i<(1<<n);i++) for(int j=0;j<n;j++)
        if(i&(1<<j))
    {
        all[i]+=v[j] ;
        all2[i]+= ( v[j]<=18 ? fac[v[j]] : 0LL ) ;
    }
 
    for(int i=0;i<(1<<n);i++)
    {
        int S0 = (i&fac_s) ;
        for(int S=S0;;S=((S-1)&S0))
        {
            LL s=all2[S]+all[i^S] ;
            int cnt=__builtin_popcount(S) ;
            if(type==1)
            {
                cnt++ ;
                while(cnt<28) mp[cnt][s]++ , cnt+=lowbit(cnt) ;
            }
            else if(cnt<=k)
            {
                int x=k-cnt+1 ;
                //ans+=mp[0][sum-s] ;
                while(x) ans+=mp[x][sum-s] , x-=lowbit(x) ;
            }
            if(!S) break ;
        }
    }
}
 
vector<int> v1,v2;
main()
{
    fac[0]=1LL ;
    for(int i=1;i<19;i++) fac[i]=(LL)fac[i-1]*i ;
    int n ;
    scanf("%d%d%lld",&n,&k,&sum) ;
    for(int i=0;i<n;i++)
    {
        int x ; scanf("%d",&x) ;
        if(i<n/2) v1.push_back(x) ;
        else v2.push_back(x) ;
    }
 
    solve(v1,1) ;
    solve(v2,2) ;
    printf("%lld\n",ans) ;
}