自动搬运

查看原文

来自洛谷，原作者为

	League丶翎 **

搬运于2025-08-24 21:46:43，当前版本为作者最后更新于2018-03-22 16:39:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

无耻的安利一波博客Chlience

这个题目我们可以画图AC

将某一个确定的上涨序列$a[1],a[2],a[3],...,a[k]$写出来

这个序列对于总数的贡献为1,当然,是当$a[k]\leq n$的时候

显然的,维持每天上涨的价格不变,由于$a[1]$能够有多种取值,那么它就会有很多贡献,当然,变化后的$a[1]$仍然要保证$a[k]\leq n$

那么能不能考虑维护一个股票价格的差分数列?就不用考虑$a[1]$的取值

并且,这个差分数列$s[1],s[2],s[3],...,s[k-1]$所做出的贡献就为$n-\sum_{i=1}^{k-1}s[i]$

一共有$m^{k-1}$个不同的差分数列,每个数列做出的贡献值为$n-\sum_{i=1}^{k-1}s[i]$

那么总贡献就为

$\sum_{d=1}^{m^{k-1}}(n-\sum_{i=1}^{k-1}s[d][i])$

将$n$提出可得

$n*m^{k-1}-\sum_{d=1}^{m^{k-1}}\sum_{i=1}^{k-1}s[d][i]$

现在要做的就是处理后面那一堆东西

注意,$s$显然是将所有可能的排列情况都算了进去,并且$s[d][i]\in[1,m]$

那么后面一共就会有$m^{k-1}*(k-1)$个数,并且在$[1,m]$中完全平均分布

所以$[1,m]$中的每个数都会出现$\frac{m^{k-1}*(k-1)}{m}=m^{k-2}*(k-1)$次

运用小学数学知识,将其总和化为$m^{k-2}*(k-1)*\frac{(m+1)*m}{2}$

这样就很好求解了

最终答案为$n*m^{k-1}-m^{k-2}*(k-1)*\frac{(m+1)*m}{2}$ 快速幂就好啦╮(╯_╰)╭

努力追赶dalao中 给予我力量吧(丢脸ing

代码如下

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,m,p,ans;
ll read() {
	ll ans=0,flag=1;
	char ch=getchar();
	while((ch>'9' || ch<'0') && ch!='-') ch=getchar();
	if(ch=='-') flag=-1,ch=getchar();
	while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
	return ans*flag;
}
ll qpow(ll a,ll b,ll mod) {
	ll ans=1;
	while(b>0) {
		if(b&1) {ans*=a;ans%=mod;}
		b>>=1;a*=a;a%=mod;
	}
	return ans;
}
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() {
	n=read(),k=read(),m=read(),p=read();
	ll x,y,gcd;
	gcd=exgcd(2,p,x,y);
	x=(x%p+p)%p;
	ans+=(qpow(m,k-1,p)*(n%p))%p;
	ans-=((((qpow(m,k-1,p)*(k-1))%p*(m+1))%p)%p*x%p);
	ans=(ans%p+p)%p;
	printf("%lld\n",ans);
	return 0;
}