专栏文章

题解：UVA13273 Making a Team

AACcepted917
UVA13273题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minz52pi
此快照首次捕获于
2025/12/02 10:43
3 个月前
此快照最后确认于
2025/12/02 10:43
3 个月前
查看原文

题解：UVA13273 Making a Team

题目传送门

前置知识：快速幂

模版题链接
快速幂，是一个在 Θ(log⁡n)\Theta(\log n) 的时间内计算 ana^n 的技巧，而暴力的计算需要 Θ(n)\Theta(n) 的时间。
计算 aa 的 nn 次方表示将 nn 个 aa 乘在一起： an=a×a⋯×a⏟n 个 aa^{n} = \underbrace{a \times a \cdots \times a}_{n\text{ 个 }a}。然而当 aa，nn 太大的时侯，这种方法就不太适用了。不过我们知道：ab+c=ab⋅ac,  a2b=ab⋅ab=(ab)2a^{b+c} = a^b \cdot a^c,\,\,a^{2b} = a^b \cdot a^b = (a^b)^2。二进制取幂的想法是，我们将取幂的任务按照指数的二进制表示来分割成更小的任务。
首先我们将 nn 表示为 22 进制，因为 nn 有 ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1 个二进制位，因此当我们知道了 a1,a2,a4,a8,…,a2⌊log⁡2n⌋a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log_2 n \rfloor}} 后，我们只用计算 Θ(log⁡n)\Theta(\log n) 次乘法就可以计算出 ana^n。
代码：
CPP
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∼5n=1 \sim 5 时的情况：
n=1n=1，答案为 11；
n=2n=2，答案为 1818；
n=3n=3，答案为 132132；
n=4n=4，答案为 680680；
n=5n=5，答案为 28802880。
借助 OEIS 查询，得到这个链接。
通项公式为
2n−4⋅n(n+1)(n2+5n−2)2 ^{n−4}\cdot n(n+1)(n^2+5n−2)

方法二

假设选出 kk 人，则答案为：
∑k=0nCnk⋅k4 \sum_{k=0}^n C_n^k \cdot k^4
然后经过一系列化简有刚才的通项公式：
2n−4⋅n(n+1)(n2+5n−2)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。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...