这个题我交了15发。。。。。。
后面7发纯属脑残,手打的poww函数快速幂,调用的时候调用成了pow
写一写我的心路历程吧
首先看到这个题,肯定是推式子无疑了!
但是菜鸡怎么会推式子呢?
打个暴力再说
打完暴力DFS枚举可能的序列,把答案交到OEIS找找规律
然后什么都没有找出来。。。。。。


那好吧,我们优化一下暴力
考虑每个点选某个数的贡献
如下(没有考虑取模)

int work(int n,int m)
{
    int ans=0,t=poww(m,n-2);
    for(int i=2;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans+=(j-1)*t+(m-j)*t*2;
    return ans;
}

我们发现,最外面的循环没什么用
可以优化成下式子

int work(int n,int m)
{
    int ans=0,t=poww(m,n-2);
    for(int j=1;j<=m;j++)
        ans+=(j-1)*t+(m-j)*t*2;
    return ans*(n-1);
}

我们发现,循环的t可以提出来
可以优化成下式子

int work(int n,int m)
{
    int ans=0,t=poww(m,n-2);
    for(int j=1;j<=m;j++)
        ans+=(j-1)+(m-j)*2;
    return ans*(n-1)*t;
}

那么我们观察ans,发现ans只与m有关
这个时候就应该推式子了,
可是数学菜鸡怎么可能推式子
先打个表
放到OEIS找找规律
图片说明
套用公式就可以得到ans
对于每次询问就可以在log内实现

完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int mod=1e9+7;
int poww(int a,int b)
{
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
int work(int n,int m)
{
    int ans=0,t=poww(m,n-2);
    m--;
    ans=3*m*(m+1)%mod*500000004%mod;
    ans=ans*(n-1)%mod*t%mod;
    return (ans+mod)%mod;
}
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int T;
signed main()
{
    cin>>T;
    while(T--)
    {
        int a,b;
        a=read();
        b=read();
        printf("%lld\n",work(a,b));
    }
    return 0;
}