2020年阿里巴巴实习笔试编程题（一）
之前思路是动态规划，结果造成计算复杂和答案错误。这里只采用排列组合，可能出现算法复杂度大的问题，还可以继续优化。
题目描述：现有n个人，从中选择任意数量的人组成一支队伍，再从这些人中选出1名队长，求不同方案数对 ∣ 1 0 9 + 7 ∣ \left\vert 10^9 +7 \right\vert ∣∣109+7∣∣的结果。如果两个方案选取的人的集合不同或选出的队长不同，则认为这两个方案是不同的。求输入任意人数 n n n得到的队伍数。
时间限制：30分钟，其中的解题思路如下：将问题分解为如下两个问题：
1、第一个子问题：从 n n n个人中能选出多少个集合，选择 1 1 1个人队伍时有 C n 1 C_n^1 Cn1种方式，选择 2 2 2个人的队伍有 C n 2 C_n^2 Cn2中方式，如此直到选择 n n n个人的队伍有 C n n C_n^n Cnn种方式。
2、第二个子问题：从每个集合中选出 1 1 1名队长，则有 i i i种方式。
3、总结规律：
当n=1时，f(1)=1;
当n=2时， f ( 2 ) = C 2 1 ⋅ 1 + C 2 2 ⋅ 2 f(2) = C_2^1\cdot 1+C_2^2\cdot 2 f(2)=C21⋅1+C22⋅2
当n=3时， f ( 3 ) = C 3 1 ⋅ 1 + C 3 2 ⋅ 2 + C 3 3 ⋅ 3 f(3) = C_3^1\cdot 1+C_3^2\cdot 2+C_3^3\cdot 3 f(3)=C31⋅1+C32⋅2+C33⋅3
…
所以 f ( n ) = C n 1 ⋅ 1 + C n 2 ⋅ 2 + . . . + C n n − 1 ⋅ n − 1 + C n n ⋅ n f(n) = C_n^1\cdot 1+C_n^2\cdot 2+...+C_n^{n-1}\cdot n-1+C_n^n\cdot n f(n)=Cn1⋅1+Cn2⋅2+...+Cnn−1⋅n−1+Cnn⋅n
##代码具体细节如下：
#include <bits/stdc++.h>
using namespace std;int func(int count);
int Cni(int x,int n);int func(int count) {if (count == 0 || count == 1) return count;int i = 1;int res=0;while (i <= count) {res+=(Cni(i, count)*i) % 100000007;i++;}return res;
}int Cni(int x,int n) {if (x == 0) {return 0;}long res1 = 1,res2=1;int i = 1;while (i <= x) {res1 *= (n - x + i)%100000007;//分子res2 *= i % 100000007;//分母i++;}res1 = res1 / res2;return res1;
}int main() {int count;cin >> count;cout << func(count) << endl;return 0;
}
运行结果如下：
