题解 UVa11609

题目大意 给定一个正整数 \(n\)，请求出所有小于 \(n\) 人的团队如果选出一个人作为队长的不同的方案数（假定这些人两两不相同）对 \(10^9+7\)取模的结果。

分析即求

\[\sum^n_{k=1}kC_n^k=\sum_{k=1}^n k\frac{n!}{k!(n-k)!}=\sum_{k=1}^nn\frac{(n-1)!}{(k-1)!(n-k)!}=n\sum_{k=1}^n C_{n-1}^{k-1}=n2^{n-1}
\]

快速幂即可。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1E+9 + 7;

int T;

ll n;

ll QuickPow(ll a, ll b, ll mod)

{

	ll res = 1;

	a %= mod;

	while(b) {

		if(b & 1) res = res * a % mod;

		a = a * a % mod;

		b >>= 1;

	}

	return res;

}

int main()

{

	scanf("%d", &T);

	int t = 0;

	while(++t <= T) {

		scanf("%d", &n);

		printf("Case #%d: %lld\n", t, n * QuickPow(2, n - 1, mod) % mod);

	}

}

巴特西

题解 UVa11609

最新文章

热门文章