Steven_MengのBlog

题目

给你$n$个数,$n≤26$,初始序列为$a_i$,$1≤a_i≤10^9$

你有$k$个$!$ ,每个$!$可以使序列中的一个数变成$a_i!$($k$不一定要用完)
例如$5!=120$

求:选出任意个数使他们和的等于$S$的方案数$(0≤S≤10^{16})$

题解

首先$20!>10^{16}$,于是当$a_i>20$的时候,不能让$a_i$变成$a_i!$
这就少了很多情况。
接下来,定义$Map[k][Sum]$为使用$k$个阶乘符号,和为$Sum$的方法数。
双向搜索即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#include <hash_map>
#define MAXN 30
#define int long long
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9') {
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9') {
x=(x*10)+(ch-'0');
ch=getchar();
}
return x*f;
}
int a[MAXN],fac[MAXN],n,k,S;
unordered_map<int,int>Map[MAXN];
inline void Init(){
fac[1]=1;
for (register int i=2;i<=20;++i){
fac[i]=fac[i-1]*i;
}
}
//三种状态:不选,选,阶乘
void dfs1(int l,int r,int Sum,int usek){
if (l>r){
Map[usek][Sum]++;
return ;
}
dfs1(l+1,r,Sum,usek);
dfs1(l+1,r,Sum+a[l],usek);
if (a[l]<=20) dfs1(l+1,r,Sum+fac[a[l]],usek+1);
}
int ans;
void dfs2(int l,int r,int Sum,int usek){
if (l>r){
for (register int i=0;i<=k-usek;++i){//还能用多少k
ans+=Map[i][S-Sum];
}
return ;
}
dfs2(l+1,r,Sum,usek);
dfs2(l+1,r,Sum+a[l],usek);
if (a[l]<=20) dfs2(l+1,r,Sum+fac[a[l]],usek+1);
}
#undef int
int main(){
#define int long long
Init();
n=read(),k=read(),S=read();
for (register int i=1;i<=n;++i){
a[i]=read();
}
dfs1(1,n/2,0,0);
dfs2(n/2+1,n,0,0);
printf("%lld\n",ans);
}

 评论