牛客算法周周练19

算法周周练19"/>

牛客算法周周练19

题目链接
题意：n个人选m 1 ≤ m ≤ n 1\le m \le n 1≤m≤n个人，再从中选一个队长，不同的队长是不同的组合，问总的组合方式的数量（模1e9+7）。
思路：即求解 ∑ i = 1 N ( i n ) \sum\limits_{i=1}^N{\dbinom i n} i=1∑N​(ni​),容易得出公式： n ∗ 2 n − 1 n*2^{n-1} n∗2n−1，注意快速幂优化就行。
AC代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod1=1e9+7;
ll n;
ll qpow(ll a,ll b){ll ans=1;while(b){if(b&1) ans=(ans*a)%mod1;a=(a*a)%mod1;b>>=1;}return ans%mod1;
}
int main() {ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;ll ans=n%mod1;cout<<(ans*qpow(2,n-1))%mod1<<endl;return 0;
}