B题 推公式

赛时一直在推公式，赛后才做出来

$n=1ans=0n=1\backslash quad\; ans=0$

$n=2ans=k^{2}n=2\backslash quad\; ans=k^2$

$n=3ans=2k^3+2k^{4}n=3\backslash quad\; ans=2k^3+2k^4$

$n=4ans=3k^4+4k^5+3k^{6}n=4\backslash quad\; ans=3k^4+4k^5+3k^6$

$n=5ans=4k^5+6k^6+6k^7+4k^{8}n=5\backslash quad\; ans=4k^5+6k^6+6k^7+4k^8$

这几个全靠手推,然后找规律

...

$ans={\sum }_{i=1}^{n-1}i(n-i)k^{n+i-1}ans=\backslash sum\_\{i=1\}^\{n-1\}i(n-i)k^\{n+i-1\}$

代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll MOD=1e9+7;
ll pow2(ll a,ll b,ll mod){ll r=1;while(b){if(b&1)r=r*a%mod;a=a*a%mod;b>>=1;}return r%mod;}
ll n,k,ans;
int main(){
    cin>>n>>k;
    ll x=pow2(k,n,MOD);
    for(int i=1;i<n;i++)
        ans=(ans+i*(n-i)%MOD*x)%MOD,x=x*k%MOD;
    cout<<ans;
}