题目链接：

---

 

年也有一个组合数学。。。(这几年的画风啊....

 

考虑直接去做：DP? DP+容斥？ 。。。。NAIVE！

 

设${a[i]}$表示第${i}$和第${i-1}$天股价差值。

那么对于任意一个可能$a$数组,它对答案的贡献为：${n-\sum a[i]}$

 

${ANS=数组A的个数*n-\sum a[i]}$

 

考虑这样的$a$数组可能有多少个？应该是：${m^{k-1}}$个,这样就计算完了减号左边。

 

考虑计算减号右边，其实相当于所有$a$数组中一共有${m^{k-1}*(k-1)}$个数字。

每一个${a[i]\in[1,m]}$,值域范围内的数字出现次数也应该一样。

每一个在${[l,r]}$的数字就出现了${m^{k-1}*(k-2)}$次。

在套一个等差数列求和公式${m^{k-1}*(k-2)*m(m+1)/2}$

 

最终：

$${ANS=n*m^{k-1}-m^{k-2}*(k-1)*m(m+1)/2}$$

 

套一个快速幂即可。

 

---

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 using namespace std; 9 #define maxn 1001010 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);12 llg n,m,k,p,ans;13 14 llg ksm(llg a,llg b,llg md)15 {16 if (b==0) return 1;17 llg mi=1;18 a%=md;19 while (b!=0)20 {21 if (b&1) mi*=a,mi%=md;22 a*=a; 23 a%=md;24 b/=2;25 }26 return mi;27 }28 29 int main()30 {31 yyj("math");32 cin>>n>>k>>m>>p;33 n%=p;34 ans=ksm(m,k-1,p)*(n % p);35 ans%=p;36 ans-=((ksm(m,k-2,p)*(k-1)) % p)*(((m*m+m)/2) % p);37 ans%=p;38 while (ans<0) ans+=p;39 cout<