直接确定第一天后面还是不太好维护,所以考虑维护差分数列。然后就是个组合数学。
#include<bits/stdc++.h> #define ll long long using namespace std; ll n,m,p,ans,k; ll ksm(ll a,ll b,ll mod) { ll res=1; while(b) { if(b&1) { res*=a; res%=mod; } a*=a; a%=mod; b>>=1; } return res; } ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } ll gcd=exgcd(b,a%b,x,y); ll t=x; x=y; y=t-(a/b)*y; } int main() { cin>>n>>k>>m>>p; ll x,y,inv; inv=exgcd(2,p,x,y); x=(x%p+p)%p; ans+=(ksm(m,k-1,p)*(n%p))%p; ans-=((((ksm(m,k-1,p)*(k-1))%p*(m+1))%p)%p*x%p); ans=(ans%p+p)%p; cout<<ans; return 0; }