Factorials and Powers of Two

• 2022 年 4 月 5 日
• 笔记
• constructive algorithms, OJ 做题题解

分析：我们可以看出这道题目的描述并不是很复杂，就是说对于一个给定的整数n，我们能否把他拆成k个powerful的数，也就是说这k个数要么是2的幂次，要么是某个数的阶乘，并且我们要让当前的k越小越好；然后如果不能被拆的话输出-1；

我们这样来看，先看会不会输出-1，我们如果把这个整数n用二进制的方法写出来，每个1都表明可以写成某个powerful的数，所以不可能输出-1；

那么我们就可以发现了k的个数就是这里二进制表示中1的个数，但是我们考虑到还有阶乘，我们令阶乘的和为s，个数为cnt，则k = cnt + F(n-s)，这里的F函数就是根据二进制找1；

既然这样我们就可以枚举每个阶乘的可能性，我们发现14！已经是最大的可能了，因为15！就已经超过了1^12的数据范围，并且我们可以发现1！和2！是不需要考虑的，因为他们和幂次是一换一的关系没有必要，所以最多只需要枚举2^12次，找到最小值即可！

那么这里的关键是在于我怎么把这么多种可能枚举出来呢，很显然不适合用dfs，所以我们这里枚举i为0~1<<12,然后再去枚举j从0~11，看i&1<<j是否存在，存在的话就让s加上factorial[j+3]，我们就是通过枚举12个位所有为0和为1的可能性，然后去看，就相当于是电路的12条并联的电路，只有对应通路的时候才会加上那条路的电阻！

代码：

1. #include<bits/stdc++.h>
2. #define INF 1100000000
3.  
4. using namespace std;
5. typedef long long LL;
6. typedef pair<LL,LL> PII;
7. LL fa[20],n;
8. int k = INF;
9.  
10. int find(LL x){
11. int cnt = 0;
12. while(x){
13. cnt += x&1;
14. x >>= 1;
15. }
16. return cnt;
17. }
18.  
19. int main()
20. {
22. int t;
23. cin >> t;
24. fa[1] = 1;
25. fa[2] = 2;
26. for(int i = 3;i<=14;i++) fa[i] = fa[i–1]*i;
27. while(t–){
28. k = 1100000000;
29. cin >> n;
30. for(int i = 0;i<(1<<12);i++){
31. int cnt = 0;
32. LL s = 0;
33. for(int j = 0;j<=11;j++){
34. if(i&(1<<j)){
35. cnt++;
36. s+=fa[j+3];
37. }
38. }
39. if(s>n) continue;
40. k = min(k,cnt + find(n – s));
41. }
42. cout << k << ‘\n’;
43. }
44. return 0;
45. }