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

NOWCODER 神秘钥匙（快速幂+二项式定理）

相关推荐