NOWCODER 神秘钥匙（快速幂+二项式定理）
链接：https://ac.nowcoder.com/acm/problem/20701
来源：牛客网
题意：
n人中选m人并在m人中选一人为队长，问有多少种选择方案
思路：
可以很容易的推出答案是
1
∗
C
n
1
+
2
∗
C
n
2
+
3
∗
C
n
3
+
.
.
.
.
.
.
+
n
∗
C
n
n
1*C_{n}^{1}+2*C_{n}^{2}+3*C_{n}^{3}+......+n*C_{n}^{n}
1∗Cn1+2∗Cn2+3∗Cn3+......+n∗Cnn
=
n
(
C
n
−
1
0
+
C
n
−
1
1
+
C
n
−
1
2
+
.
.
.
.
.
.
+
C
n
−
1
1
)
=n(C_{n-1}^{0}+C_{n-1}^{1}+C_{n-1}^{2}+......+C_{n-1}^{1})
=n(Cn−10+Cn−11+Cn−12+......+Cn−11)(利用推论：
m
C
n
m
=
n
C
n
−
1
m
−
1
mC_{n}^{m}=nC_{n-1}^{m-1}
mCnm=nCn−1m−1)
=
n
∗
2
n
−
1
=n*2^{n-1}
=n∗2n−1(二项式定理)
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll n;
ll qpow(ll a,ll b) { //快速幂模板
ll res = 1,base = a;
while(b) {
if(b&1) res = res*base%mod;
base = base*base%mod;
b >>= 1;
}
return res;
}
int main() {
cin>>n;
cout<<(n*qpow(2,n-1))%mod;
}
本文地址：https://blog.csdn.net/cat_hate_fish/article/details/109249773