题目
题目链接：https://www.luogu.com.cn/problem/P3228
小 T 最近在学着买股票，他得到内部消息：F 公司的股票将会疯涨。股票每天的价格已知是正整数，并且由于客观上的原因，最多只能为 (n)。在疯涨的 (k) 天中小 T 观察到：除第一天外每天的股价都比前一天高，且高出的价格（即当天的股价与前一天的股价之差）不会超过 (m)，(m) 为正整数。并且这些参数满足 (m(k-1)<n)。小 T 忘记了这 (k) 天每天的具体股价了，他现在想知道这 (k) 天的股价有多少种可能。
(m,k,pleq 10^9;nleq 10^{18})。
思路
不难想到把每天的股价差分一下。那么现在问题转化为对于一个长度为 (k-1) 的序列 (a)，且 (a) 的每一个元素都不超过 (m)，它的贡献是 ((n-sum^{i=1}_{k-1}a_i))。求所有满足要求的序列的贡献之和。
显然差分序列一共有 (m^{k-1}) 种。记 (a_{i,j}) 为第 (i) 种差分序列的第 (j) 个元素。那么答案即为
[sum^{m^{k-1}}_{i=1}left ( n-sum_{j=1}^{k-1}a_{i,j}
ight )
]
[=n imes m^{k-1}-sum^{m^{k-1}}_{i=1}sum_{j=1}^{k-1}a_{i,j}
]
考虑减号后面一部分。也就是所有差分序列的所有元素和。
可以发现每一个 ([1,m]) 间的数字的出现次数都是一样的。因为对于两个数字 (x,y)，我们把所有差分序列中 (x) 和 (y) 的位置交换，那么这 (m^{k-1}) 个差分序列必然和没有交换前的一致。
由于所有数字出现次数之和为 (m^{k-1} imes (k-1))，所以每一个数字的出现次数就为 (m^{k-2} imes (k-1))。所以答案就是
[n imes m^{k-1}-frac{m(1+m)}{2} imes m^{k-2} imes (k-1)
]
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k,p;
ll fpow(ll x,ll k)
{
ll ans=1;
for (;k;k>>=1,x=x*x%p)
if (k&1) ans=ans*x%p;
return ans;
}
int main()
{
scanf("%lld%lld%lld%lld",&n,&k,&m,&p);
printf("%lld",(n%p*fpow(m,k-1)%p-fpow(m,k-2)*(k-1)%p*((1+m)*m/2%p)%p+p)%p);
return 0;
}