HNOI2013 数列

题面

设第i天到第i+1天的涨幅为\(a_i\)，容易得到柿子：

\[Ans=\sum_{a_1=1}^m\sum_{a_2=1}^m\dots\sum_{a_{k-1}=1}^m(n-\sum_{i=1}^{k-1}a_i)\]

但是跑不过。

所以需要展开柿子： \[ \begin{align} Ans &= \sum_{a_1=1}^m\sum_{a_2=1}^m\dots\sum_{a_{k-1}=1}^m(n-\sum_{i=1}^{k-1}a_i)\\\\ &= nm^{k-1}-\sum_{a_1=1}^m\sum_{a_2=1}^m\dots\sum_{a_{k-1}=1}^m\sum_{i=1}^{k-1}a_i\\\\ &= nm^{k-1}-\sum_{i=1}^{k-1}\sum_{a_1=1}^m\sum_{a_2=1}^m\dots\sum_{a_{k-1}=1}^ma_i\\\\ &= nm^{k-1}-(k-1)m^{k-2}\sum_{i=1}^{m}i\\\\ &= nm^{k-1}-(k-1)m^{k-2}\frac{m(m+1)}{2}\\\\ \end{align} \]

然后就是快速幂了。

ll fpm(ll a,ll b,ll p){
    ll c=1;
    while(b){
        if(b&1)c=c*a%p; 
        a=a*a%p;
        b>>=1;
    }
    return c;
}
int main(){
#ifdef cnyali_lk
    freopen("3228.in","r",stdin);
    freopen("3228.out","w",stdout);
#endif
    ll n,m,k,p;
    n=read();//read是读入
    k=read()-1;
    m=read();
    p=read();
    n%=p;
    printf("%lld\n",(n*fpm(m,k,p)%p-fpm(m,k-1,p)*k%p*(m*(m+1)/2%p)%p+p)%p);
    return 0;
}