题解：UVA13273 Making a Team
ACcepted917
·
·
题解
题解：UVA13273 Making a Team
题目传送门
前置知识：快速幂
模版题链接
快速幂，是一个在 \Theta(\log n) 的时间内计算 a^n 的技巧，而暴力的计算需要 \Theta(n) 的时间。
计算 a 的 n 次方表示将 n 个 a 乘在一起： a^{n} = \underbrace{a \times a \cdots \times a}_{n\text{ 个 }a}。然而当 a，n 太大的时侯，这种方法就不太适用了。不过我们知道：a^{b+c} = a^b \cdot a^c,\,\,a^{2b} = a^b \cdot a^b = (a^b)^2。二进制取幂的想法是，我们将取幂的任务按照指数的二进制表示来分割成更小的任务。
首先我们将 n 表示为 2 进制，因为 n 有 \lfloor \log_2 n \rfloor + 1 个二进制位，因此当我们知道了 a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log_2 n \rfloor}} 后，我们只用计算 \Theta(\log n) 次乘法就可以计算出 a^n。
代码：
typedef long long ll;
ll fpm(ll x,ll power){
x%=mod;
ll ans=1;
for(;power;power>>=1,(x*=x)%=mod)
if(power&1)(ans*=x)%=mod;
return ans%mod;
}
分析
方法一
不难得出 n=1 \sim 5 时的情况：
$n=2$，答案为 $18$；
$n=3$，答案为 $132$；
$n=4$，答案为 $680$；
$n=5$，答案为 $2880$。
借助 [OEIS](https://oeis.org/) 查询，得到这个[链接](https://oeis.org/A058649)。
通项公式为
$$2 ^{n−4}\cdot n(n+1)(n^2+5n−2)$$
#### 方法二
假设选出 $k$ 人，则答案为：
$$ \sum_{k=0}^n C_n^k \cdot k^4$$
然后经过一系列化简有刚才的通项公式：
$$2 ^{n−4}\cdot n(n+1)(n^2+5n−2)$$
~~至于是如何化简的，蒟蒻不会，向各位 dalao 求教。~~
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=1e8+7;
typedef long long ll;
ll fpm(ll x,ll power){//快速幂
x%=mod;
ll ans=1;
for(;power;power>>=1,(x*=x)%=mod)
if(power&1)(ans*=x)%=mod;
return ans%mod;
}
ll n;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
while(1){
cin>>n;
if(n==0){
return 0;
}
if(n==1){
cout<<"1\n";
continue;
}else if(n==2){
cout<<"18\n";
continue;
}else if(n==3){
cout<<"132\n";
continue;
}else if(n==4){
cout<<"680\n";
continue;
}else if(n==5){
cout<<"2880\n";
continue;
}
cout<<fpm(2,n-4)*n%mod*(n+1)%mod*(1ll*fpm(n,2)+1ll*5*n-2)%mod<<'\n';
}
return 0;
}
``````
感谢管理员审核qwq。