---

题目传送门

---

前言

这道题最难的其实是想到把 【构造一个上升序列】 转化为 【构造一个差分序列】（当然我是想不到的，所以看了题解的一部分）。
了解此思路下的我经过一顿推公式之后 依旧只推出了 30pts 的暴力公式和代码，然后看了题解 豁然开朗，所以决定写一篇题解来说说暴力和正解的思路。

---

整体思路

正如前言所说，我们把每一天股票增长的差分数组 $d_i$ 设出来，$d_i$ 的取值范围是 $[1,m]$。
假设我们已经构造出了 $[1,k-1]$ 天的差分数组 $d_{\mathrm{1...}k-1}$，那么最后一天就有 $n-{\sum }_{i=1}^{k-1}{d}_i$ 种可能。

那这个式子有没有可能小于等于 $0?$
答案是否定的，因为题目中规定了数据范围 $m\times (k-1)<n$，只要 $d_i$ 取值合法，那这个式子就大于 $0$ 。

由于对于我们所构造的 $[1,k-1]$ 的差分数组一共有 $m^{k-1}$ 个，所以总的方案数就是：
$$\sum _{i=1}^{m^{k-1}}n-sum{d}_i=n\times m^{k-1}-\sum _{i=1}^{m^{k-1}}sum{d}_i$$
其中，$sum{d}_i$ 表示构造的第 $i$ 个差分序列的 $d$ 值之和。

现在看来不好处理的就是后面这个和式，下来我将讲述暴力和正解两种思路。

---

暴力

我们尝试使用常常用来求和式的贡献法。

对于一个数 $x\in [1,m]$，我们考虑它的出现次数。
假设在一些序列中 $x$ 出现了 $i$ 次，那这样的序列有多少个呢 ?
答案是 $C_{k-1}^i\times (m-1{)}^{k-i-1}$ 次：$C_{k-1}^i$ 表示从 $k-1$ 个位置中选出 $i$ 个放 $x$，剩下的位置共 $k-i-1$ 个。由于 $i$ 个 $x$ 已经放完，所以剩下的位置每个只有 $m-1$ 种选择（就是还可以放 $[1,m]$ 中除去 $x$ 后剩下的数），所以一共有 $C_{k-1}^i\times (m-1{)}^{k-i-1}$ 种选择。
那么出现 $i$ 个 $x$ 的所有序列的贡献就是 $x\times ({\sum }_{i=1}^{k-1}i\times C_{k-1}^i\times (m-1{)}^{k-i-1})$

那么总答案就是：
$$\begin{gathered} n\times m^{k-1}-\sum _{i=1}^{m^{k-1}}sum{d}_i=n\times m^{k-1}-(\sum _{x=1}^{m}x\times (\sum _{i=1}^{k-1}i\times C_{k-1}^i\times (m-1{)}^{k-i-1})) \\ =n\times m^{k-1}-(\frac{m\times (m+1)}{2}\times (\sum _{i=1}^{k-1}i\times C_{k-1}^i\times (m-1{)}^{k-i-1})) \end{gathered}$$

时间复杂度

$O(n\times log(p))$，期望得分 $30pts$ 。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 2e4 + 7;

ll n, m, p, k;
ll fac[maxn], inv[maxn];
ll qpow(ll x, ll y) {
	ll res = 1;
	for (; y; y >>= 1, x = x * x % p)
		if (y & 1) res = res * x % p;
	return res;
}
ll C(ll x, ll y) {return fac[x] * inv[x - y] % p * inv[y] % p;}
int main() {
	fac[0] = inv[0] = 1;
	scanf("%lld%lld%lld%lld", &n, &k, &m, &p);
	for (ll i = 1; i <= n; ++i) {
		fac[i] = fac[i - 1] * i % p;
		inv[i] = qpow(fac[i], p - 2);
		// 从数据来看, 所有 p 应该都是质数, 否则这个逆元就是错的（滑稽
	}
	ll tmp = 0;
	for (ll i = 1; i <= k - 1; ++i)
		tmp = (tmp + i * C(k - 1, i) % p * qpow(m - 1, k - 1 - i) % p) % p;
	tmp = (tmp * m * (m + 1) / 2) % p;
	printf("%lld\n", (n * qpow(m, k - 1) % p - tmp + p) % p);
	return 0;
}

---

正解

其实这题求和式的值并不需要贡献法。

不考虑重复，构造的 $m^{k-1}$ 个序列中共有 $m^{k-1}\times (k-1)$ 个数。
由每个数的对称性可知：$[1,m]$ 中的每个数的出现次数相等。所以一个数 $x$ 的出现次数为 $\frac{m^{k-1}\times (k-1)}{m}=m^{k-2}\times (k-1)$。
那么正解公式就可以呼之欲出了：
$$n\times m^{k-1}-\sum _{i=1}^{m^{k-1}}sum{d}_i=n\times m^{k-1}-\frac{m\times (m+1)}{2}\times m^{k-2}\times (k-1)$$
代码实现就是快速幂了。

感觉正解公式的技术含量还不如暴力公式的高

时间复杂度

$O(log(k))$，期望得分 $100pts$ 。

代码

#include <bits/stdc++.h>

namespace FIO {
	template<typename T> T rd() {
		T x = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
		while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
		return x * f;
	}
	template<typename T> void wrt(T x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) wrt(x / 10);
		putchar(x % 10 + 48);
	}
};

using namespace std;
using namespace FIO;

typedef __int128 ll;

const int maxn = 1e6 + 7;

ll n, m, mod, k, ans;
ll qpow(ll x, ll y) {
	ll res = 1;
	for (; y; y >>= 1, x = x * x % mod)
		if (y & 1) res = res * x % mod;
	return res;
}
int main() {
	n = rd<ll>(), k = rd<ll>(), m = rd<ll>(), mod = rd<ll>();
	ans = ((n * qpow(m, k - 1) - 
			m * (m + 1) / 2 * qpow(m, k - 2) * (k - 1)) % mod + mod) % mod;
	wrt(ans);
	return 0;
}