这个题我交了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; }