C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 480K, 提交时间: 2019-09-03 20:27:54

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,m,p;
ll qpow(ll a,ll n,ll mod){
	ll ans = 1;
	while(n){
		if(n & 1)	ans = ans * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return ans;
}
int main(){
	cin>>n>>k>>m>>p;
	n %= p;
	ll ans1 = n * qpow(m,k - 1,p) % p;
	ll ans2 = (qpow(m,k - 2,p) * ((m * (m + 1) / 2) % p)) % p;
	ans2 = (k - 1) * ans2 % p;
	cout<<(ans1 - ans2 + p) % p<<endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 464K, 提交时间: 2019-11-01 19:11:38

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll gg(ll a,ll b,ll p){
	ll ret=1;
	while(b){
		if(b&1)ret=(ret*a)%p;
		a=(a*a)%p;b>>=1;
	}
	return ret;
}
ll n,k,m,p,ans; 
int main(){
	scanf("%lld%lld%lld%lld",&n,&k,&m,&p);n%=p;
	ans=n*gg(m,k-1,p)%p;
	ans-=gg(m,k-2,p)*(k-1)%p*(m*(m+1)/2%p)%p;
	printf("%lld",(ans+p)%p);
	return 0;
}