题解 CF525E 【Anya and Cubes】 双向搜索 哈希表

   考虑暴力。    在这个题中，每个数有3种决策，分别是**不选、选上、加阶乘且选上**。根据样例，这个题好像没有考虑加阶乘且不选的情况，在统计答案时少进入一种情况就可以了。    如果每个数有三种决策，那么完全枚举的话时间复杂度是$3^n$，当$n=26$时是无法通过的。而因为我们要求的是等式左边（若干个数之和）等于等式右边（给定值）。所以我们可以考虑先搜前$\lfloor \frac n2\rfloor$个，再搜后$\lceil \frac n2\rceil$个。把前面搜出来的结果挂到一个hash表上，每次搜到相同的值++。    hash就是压缩了空间使得数据范围很大的但是个数不是特别大的数被存在一个较小的空间里，每次查询一个数就要去它模一个固定数的余数的那个剩余系中去找有没有相应的数。    同时，在搜索的过程中，我们如果保证每次数值都会改变（即不搜0的情况），那么到一个dfs阶段，都可以统计一次答案，表示没被搜到的都是0。相当于一棵dfs树上的每个节点都统计了答案，这样减少了冗余0的叶子，优化了常数。    因为$S≤10^{16}$，而$18! \le 10^{16}\le 19!$，所以添加阶乘的数，只能不超过18。因此long long预处理出18以内的阶乘。对于$O(3^\frac n2)$的复杂度，可行性剪枝就没有必要了（如果搜到的数已经大于S就一定不合法），所以我没有加。 ```cpp #include<cstdio> #include<cstring> struct node//链表 { long long n; int v; node *nxt; node(long long n,int v) { this->n=n; this->v=v; nxt=NULL; } node() { nxt=NULL; } }head[27][100003],*tail[27][100003]; long long a[30],s,n,k; long long fct[20],now; void dfs(int x,int num)//前一半 { int flag=0; long long tmp=now%100003; node *p=&head[num][tmp]; while(p->nxt) { p=p->nxt; if(p->n==now) { p->v++; flag=1; break; } } if(flag==0) { tail[num][tmp]->nxt=new node(now,1); tail[num][tmp]=tail[num][tmp]->nxt; } if(x>n/2) return; for(int i=x;i<=n/2;i++) { now+=a[i]; dfs(i+1,num);//可以加可行性剪枝 now-=a[i]; if(a[i]<=18)//判断范围 { now+=fct[a[i]]; dfs(i+1,num+1); now-=fct[a[i]]; } } } long long sum=0; void dfs2(int x,int num) { for(int i=0;i<=k-num;i++)//查表 { node *p=&head[i][((s-now)%100003+100003)%100003]; while(p->nxt) { p=p->nxt; if(p->n==s-now) { sum+=p->v; break; } } } if(x>n) return; for(int i=x;i<=n;i++) { now+=a[i]; dfs2(i+1,num); now-=a[i]; if(a[i]<=18) { now+=fct[a[i]]; dfs2(i+1,num+1); now-=fct[a[i]]; } } } int main() { fct[0]=1; for(int i=0;i<100003;i++) for(int j=0;j<=26;j++) tail[j][i]=&head[j][i]; for(int i=1;i<=18;i++) fct[i]=fct[i-1]*i; scanf("%d%d%lld",&n,&k,&s); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n/2;i++)//搜前一半 { now=a[i]; dfs(i+1,0); if(a[i]<=18) { now=fct[a[i]]; dfs(i+1,1); } } tail[0][0]->nxt=new node(0,1);//算一种0的情况 tail[0][0]=tail[0][0]->nxt; for(int i=n/2+1;i<=n;i++) { now=a[i]; dfs2(i+1,0); if(a[i]<=18) { now=fct[a[i]]; dfs2(i+1,1); } } now=0; dfs2(n+1,0);//同样算一种0的情况 printf("%I64d\n",sum); return 0; } ```