BZOJ- 3142：数列 （数学）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,M,K,P,ans,ans2;
ll qpow(ll a,ll x){
    ll res=1;while(x){
        if(x&1) res=(ll)res*a%P;
        a=(ll)a*a%P; x>>=1;
    }return res;
}
int main()
{
    scanf("%lld%lld%lld%lld",&N,&K,&M,&P); N%=P;
    ans=(ll)N*qpow(M,K-1)%P;
    ll a=M,b=M+1;
    if(a&1) b/=2; else a/=2;
    ans2=(ll)a*b%P;
    ans2=(ll)ans2*qpow(M,K-2)%P*(K-1)%P;
    ans=(((ans-ans2)%P)+P)%P;
    printf("%lld\n",ans);
    return 0;
}