Problem

小 T 最近在学着买股票，他得到内部消息：F 公司的股票将会疯涨。股票每天的价格已知是正整数，并且由于客观上的原因，最多只能为 N。在疯涨的 K 天中小 T 观察到：除第一天外每天的股价都比前一天高，且高出的价格（即当天的股价与前一天的股价之差）不会超过 M，M 为正整数。并且这些参数满足 M(K-1)<N。小 T 忘记了这 K 天每天的具体股价了，他现在想知道这 K 天的股价有多少种可能

$M,\ K,\ P \leq 10^9,\ N \leq 10^{18}$
本题很贴心地没有提醒，P 可能不为质数，但一定为奇数

Solution

设计一个平面直角坐标系。纵坐标为股价，横坐标为第 x 天，整点上用数字表示方案数。

从 1 天开始，假设股价走的折线到第 k 天是一条道路，题目需要你统计道路的个数。
假设 m =2，第一天价格为 1，我们把这个道路和方案数画出来，发现很像斜着的杨辉三角。

那么考虑 m 不为 2 的情况。则第一天方案数为 $1$, 第二天方案数为 $m$。第三天由于方案数的每个 1（每一条现已经发展的道路）都会有贡献，则第三天方案数为 $m^2$。以此类推，第 k 天方案数为 $m^{k-1}$。

显然这个方案数三角的第 k 天一列，是一列按股价从上到下排的数字。而这列数字由于类似杨辉三角的性质，是对称的。

那么假设第一天价格为 1。那么到了第 k 天后，这列数字的顶端（即股价最大值）是 $1+m(k-1)$，这列数字的底端则是 $1+k$。由于题面说明参数满足 $M(K-1) < N$，则 $M(K-1)+1 \leq N$。也就是我们统计的三角形方案数，在第一天价格为 1 的时候，是绝对合法的。因此我们得到了价格为 1 的方案数 $M^{K-1}$。那么到一开始价格为 2, 价格为 3, 同时最后一列数也会向上移一格。一直下去我们会发现那列数会触及到 n 的限制。

当触及到了限制以后，那列数仍会往上走。超过这个限制的方案数我们则不会统计。
你可以画个图。由于对称，我们可以把跨界的方案数全部相加除以二。由于不好画图，细节还是自己想吧。

然后最终我们得到的方案如下：
令第 k 列数的和为 $W=m^{k-1}$

则未触及 N 的方案数为 $ansa=W(n-m(k-1))$

触及了 N 的方案数为 $ansb=\frac {W(mk-m-k+2)}{2}=\frac {W(m-1)(k-1)}{2}$

最终总方案数为 $ans=ansa+ansb=W(n-m(k-1))+\frac {W(m-1)(k-1)}{2}$

我调了一下午，最终发现错在求逆元处。

Code

// Code by ajcxsu
// Problem: sequence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,k,m,p;
template<typename T> void gn(T &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

ll qpow(ll x,ll y) {
    x%=p;
    ll ret=1;
    while(y) {
        if(y&1) ret=(ret*x)%p;
        x=(x*x)%p;
        y>>=1;
    }
    return ret;
}

void exgcd(ll a,ll b,ll &x, ll &y) {
    if(!b) {
        x=1, y=0;
        return;
    }
    ll xb,yb;
    exgcd(b,a%b,xb,yb);
    x=yb, y=xb-a/b*yb;
}

ll inv(ll x) {
    ll n1,n2;
    exgcd(x,p,n1,n2);
    return n1;
}

int main() {
    gn(n),gn(k),gn(m),gn(p);
    ll W=qpow(m,k-1);
    ll ans=((n-m*(k-1))%p)*W;
    ans%=p;
    ll ansb;
    ansb=W*(k-1), ansb%=p;
    ansb*=m-1, ansb%=p;
    ansb*=inv(2), ansb%=p;
    ans=((ans+ansb)%p+p)%p;
    printf("%lld\n",(long long)ans);
    return 0;
}