Luogu

BZOJ

分析

设 $a$ 为差分数组，然后大力推式子：

$$ \begin{aligned} ans=&\sum\limits_{a_1=1}^m\sum\limits_{a_2=1}^m...\sum\limits_{a_{k-1}=1}^m(n-\sum\limits_{i=1}^{k-1}a_i)\\ =&nm^{k-1}-\sum\limits_{a_1=1}^m\sum\limits_{a_2=1}^m\ldots\sum\limits_{a_{k-1}=1}^m\sum\limits_{i=1}^{k-1}a_i\\ =&nm^{k-1}-(k-1)m^{k-2}\sum\limits_{i=1}^m i\\ =&nm^{k-1}-(k-1)m^{k-2}\frac{m(m+1)}{2}\end{aligned} $$

然后快速幂搞一下即可。注意取膜。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline ll read() {
    ll X=0; int w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

ll n,k,m,p;

inline int fastpow(ll a,ll b,ll ans=1) {
    for (;b;b>>=1,a=a*a%p)
        if (b&1) ans=ans*a%p;
    return ans;
}

int main() {
    n=read(),k=read(),m=read(),p=read(); n%=p;
    printf("%lld\n",(n*fastpow(m,k-1)%p-fastpow(m,k-2)*(k-1)%p*(m*(m+1)/2%p)%p+p)%p);
    return 0;
}