专栏文章

水上舞者索尼娅

AAndy1101
P11465题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@miqm2fst
此快照首次捕获于
2025/12/04 07:01
3 个月前
此快照最后确认于
2025/12/04 07:01
3 个月前
查看原文

题目传送门

思路

由题我们可以知道答案为 ∑i=1n(k+1)i\sum\limits_{i = 1}^{n} (k+1)^{i}。但是我们需要优化两个点——幂的运算和循环。
  1. 优化幂的运算，这里我们需要用到快速幂，作用是用来快速算出 aba^b。
    核心代码：
    CPP
    int ksm(int a,int b) //注意运算时要取模
{
	int ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=ans*a%P;
		}
		a=a*a%P;
		b=b/2;
	}
	return ans;
}
  2. 优化循环，这里我们需要用到等比数列求和公式来进行求和：(k+1)×[(k+1)n−1]k+1\dfrac{ (k+1) \times [ (k+1)^n - 1]}{k+1}。

AC Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int P=1e9+7;
int ksm(int a,int b)
{
	int ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=ans*a%P;
		}
		a=a*a%P;
		b=b/2;
	}
	return ans;
}
signed main()
{
	int t;
	cin >>t;
	while(t--)
	{
		int n,k;
		cin >>n>>k;
		int ans;
		int a=k+1;
		ans=((ksm(k+1,n+1)-1)*ksm(k,P-2)-1)%P;
		cout <<ans<<'\n';
	}
	return 0;
}

评论

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

正在加载评论...