问题描述

​ G 将军有一支训练有素的军队，这个军队除开 G 将军外，每名士兵都有一个直接上级（可能是其他士兵，也可能是 G 将军）。现在 G 将军将接受一个特别的任务，需要派遣一部分士兵（至少一个）组成一个敢死队，为了增加敢死队队员的独立性，要求如果一名士兵在敢死队中，他的直接上级不能在敢死队中。
​ 请问，G 将军有多少种派出敢死队的方法。注意，G 将军也可以作为一个士兵进入敢死队。

​ 输入格式:
​ 输入的第一行包含一个整数 n，表示包括 G 将军在内的军队的人数。军队的士兵从 1 至 n 编号，G 将军编号为 1。
接下来 n-1 个数，分别表示编号为 2, 3, …, n 的士兵的直接上级编号，编号 i 的士兵的直接上级的编号小于 i。
​ 输出格式:
​ 输出一个整数，表示派出敢死队的方案数。由于数目可能很大，你只需要输出这个数除 10007 的余数即可。

​ 样例输入 1:
​ 3
​ 1 1

​ 样例输出 1:
​ 4

​ 样例说明:
​ 这四种方式分别是：

  1. 选 1；

  2. 选 2；

  3. 选 3；

  4. 选 2, 3。

样例输入 2:
7
1 1 2 2 3 3

样例输出 2:
40

数据规模与约定

  • 对于 20% 的数据，n ≤ 20；
  • 对于 40% 的数据，n ≤ 100；
  • 对于 100% 的数据，1 ≤ n ≤ 100000。

资源约定：

  • 峰值内存消耗 < 256M
  • CPU 消耗 < 2000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main 函数需要返回 0
注意：只使用 ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意：所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

思路

1、首先将所有士兵直属上级的编号放于数组 a；
2、每个人有两种选择，去和不去，用 0 和 1 表示，转换为二进制放于数组 b；
3、最后判断每个士兵是不是与其直属上级同时执行任务，进而对 count 进行统计。

代码实现

//
//  main.c
//  派遣敢死队问题
//
//  Created by Canvas on 2018/12/31.
//  Copyright © 2018 Canvas. All rights reserved.
//

#include <stdio.h>
#include <math.h>

int main() {
    int number;
    int count=0;
    int flag;
    scanf("%d",&number);//派遣的人数
    
    int i,j;
    int temp;
    int a[number],b[number];//a
    a[0]=0;//将军
    
    for(i=1;i<number;i++){
        scanf("%d",&a[i]);//每个人的直属上级
    }
    
    for(i=1;i<pow(2,number);i++){
        temp=i;
        for(j=0;j<number;j++){
            //遍历所有情况
            b[j]=temp%2;
            temp/=2;
        }
        
        flag=1;
        for(j=1;j<number;j++){
            //将军没有上级，不用判断
            if(b[j]==1&&b[a[j]-1]==1){
                //判断是否士兵和上级同时执行任务
                //b[j]为编号为j+1的士兵去不去
                //b[a[j]-1]为编号为j+1的士兵的直接上级去不去
                flag=0;
                break;
            }
        }
        
        if(flag==1)
            count++;
    }
    
    printf("%d\n",count);
    return 0;
}