3481. 阶乘的和
问题重述:
给定一个非负整数 n,请你判断是否存在一些整数 xi,能够使得 n=∑1≤i≤txi!,其中 t≥1,xi≥0,xi=xj iff i=j。
iff 表示当且仅当。
输入格式
输入包含多组测试数据。
每组数据占一行,包含一个非负整数 n。
最后一行是一个负数,表示输入结束,无需处理。
输出格式
每组数据输出一行结果,如果 n 能表示为若干数的阶乘之和,则输出 YES
,否则输出 NO
。
数据范围
0≤n≤106,
每组输入最多包含 100 组数据。
输入样例:
9
-1
输出样例:
YES
问题分析:
这道题要求给出一个整数,让我们判断有没有一些数的阶乘之和刚好等于这个整数,题目给定的条件中,整数范围为0≤n≤10^6,9的阶乘等于362800已经可以满足这个范围,那么我们就可以把这道题转化为给定一个整数,我们能否在09的阶乘中找到几个数让他们的和等于这个整数,我们可以把09阶乘的所有和枚举出来,将给定的整数进行比对,即可得出结果
解法:
二进制枚举、dfs枚举
解题:
二进制代码和dfs代码都在其中:
package cn.basic.算法;
import java.util.HashSet;
import java.util.Scanner;
/**
* 给定一个非负整数 n,请你判断是否存在一些整数 xi,能够使得 n=∑1≤i≤txi!,其中 t≥1,xi≥0,xi=xj iff i=j。
*
* iff 表示当且仅当。
*
* 输入格式
* 输入包含多组测试数据。
*
* 每组数据占一行,包含一个非负整数 n。
*
* 最后一行是一个负数,表示输入结束,无需处理。
*
* 输出格式
* 每组数据输出一行结果,如果 n 能表示为若干数的阶乘之和,则输出 YES,否则输出 NO。
*
* 数据范围
* 0≤n≤106,
* 每组输入最多包含 100 组数据。
*
* 输入样例:
* 9
* -1
* 输出样例:
* YES
*/
public class Main7 {
// 创建一个阶乘数组
public static int[] arrays = new int[10];
public static int n;
public static HashSet<Integer> set = new HashSet<>();
public static void main(String[] args) {
// 初始化阶乘数组
arrays[0] = arrays[1] = 1;//0的阶乘为1
for (int i = 2; i < 10; i++) {
arrays[i] = i * arrays[i-1];
}
//dfs枚举方法
//dfs(0,0,arrays);
//二进制枚举方法
for (int i = 0; i<1024; i++) {//i<1024也可以写成i<1<<10,意思相同
int sum = 0;
for (int j = 0; j < 10; j++) {
//需要知道num>>j&1 == 1 的时候,num对应的二进制数上对应第j位为1
if ((i>>j&1) == 1){
sum += arrays[j];
}
}
//需要注意0不能被加入set集合,因为t>=1
if (sum !=0){set.add(sum);}
}
Scanner scanner = new Scanner(System.in);
while (true){
n = scanner.nextInt();
// 如果遇见1退出
if (n < 0){
break;
}
if (set.contains(n)){
System.out.println("YES");
}else {
System.out.println("NO");
}
}
}
public static void dfs(int sum,int n,int[]c){
if (sum > 0){
set.add(sum);
}
for (int i = n;i < 10; i++) {
sum += c[i];
dfs(sum,i+1,c);
sum -=c[i];
}
}
}
代码解析:
首先创建一个阶乘数组,依次存入0~9的阶乘,使用阶乘数组进行组合,和加入HashSet集合中(去重),对输入的n进行判断。阶乘数组组合有两种方式,一种二进制,一种dfs枚举。
二进制方式:我们的阶乘数组长度为10,取值为则令对应二进制位为1,不取为0,那么总共有2^10也就是1024种可能,0000000000表示都不取(因为t>=1要把这种可能性剔除),1111111111表示都取。然后将这1024种可能性的阶乘和都求出来,加入HashSet集合中去,我们这个时候就需要知道十个数中哪些被选中,当op>>j&1的值为1时,表示op的二进制下第j位上的数是1,我们根据这个来判断哪些数可选,1024个数依次进行计算,对每个数的10个二进制位数进行一次遍历,为1的则把相加求和,把结果加入集合中去,计算完毕将总和置为0开始计算下一个数,计算时需要注意,全部为0的这种可能不能加入集合。
dfs方式:每一次方法开始进行条件判断,如果总和大于0,则加入集合中,其中会有多次重复加入,但是set集合可以去重。从当前节点开始循环,更新总和,进入下一个节点,进行递归,每当一个方法结束以后,要减掉当前加上的阶乘值,我们可以通过这样的方式得到所有的可能组合。这种枚举方法时间复杂度较高,容易超时,不建议使用这种方法。
二进制枚举总结:
一般适用于只有取和不取两种可能性的题目,将每一种可能性都列出来,取则令对应二进制位为1,否则令对应二进制位为0,我们需要对某个数的对应二进制的每一位进行判断,通过这个判断来得知是否取这个位上对应的数字,判断方法:当op>>j&1的值为1时,表示op的二进制下第j位上的数是1
// 对有n个可能选择的二进制枚举模板
for (int i = 0; i<1<<n; i++) {//i<1024也可以写成i<1<<10,意思相同
for (int j = 0; j < n; j++) {
//需要知道num>>j&1 == 1 的时候,num对应的二进制数上对应第j位为1
if ((i>>j&1) == 1){
//对应二进制位上的数位1,则进行处理,例如求和
}
}
}