水上舞者索尼娅

Andy1101 · 2024-12-31 22:04:00 · 题解

题目传送门

思路

由题我们可以知道答案为 \sum\limits_{i = 1}^{n} (k+1)^{i}。但是我们需要优化两个点——幂的运算和循环。

1. 优化幂的运算，这里我们需要用到快速幂，作用是用来快速算出 a^b。
   核心代码：

   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. 优化循环，这里我们需要用到等比数列求和公式来进行求和：\dfrac{ (k+1) \times [ (k+1)^n - 1]}{k+1}。

AC Code：

#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;
}