题解

思路分析

这是一道 组合数学 + 矩阵快速幂 的计数问题。

问题建模

• $K$ 天股价，第一天在 $[1, N]$ 范围内
• 每天比前一天高，且高出不超过 $M$
• 求方案数模 $P$

核心思路

1. 差分数组

设第 $i$ 天股价为 $s_i$，定义差分数组：

$$d_i = s_i - s_{i-1} \quad (i \geq 2)$$

则有：

• $1 \leq d_i \leq M$
• $s_K = s_1 + \sum_{i=2}^{K} d_i$
• $s_K \leq N$

2. 容斥原理计数

固定 $s_1$，问题转化为：

$$\sum_{i=2}^{K} d_i \leq N - s_1$$

其中 $1 \leq d_i \leq M$。

这等价于计数：有多少个长度为 $K-1$ 的序列，每个元素在 $[1, M]$ 内，和 $\leq N - s_1$。

使用组合数学：

$$\text{方案数} = \sum_{sum=K-1}^{\min(M(K-1), N-s_1)} C_{sum-1}^{K-2} $$

3. 求和优化

对 $s_1$ 求和：

$$\text{总方案数} = \sum_{s_1=1}^{N} \text{方案数}(s_1)$$

通过推导，可以化简为：

$$\text{答案} = M^{K-2} \times (N \cdot M - \frac{M(M+1)}{2}(K-1)) $$

4. 快速幂

$M^{K-2}$ 使用快速幂计算（$K$ 可能很大）。

算法步骤

1. 公式推导：

   • 化简为组合数求和
   • 得到闭式公式

2. 快速幂计算：

   • 计算 $M^{K-2} \bmod P$

3. 计算答案：

   • 套用公式，注意取模

4. 输出结果

复杂度分析

• 时间复杂度：$O(\log K)$
• 空间复杂度：$O(1)$

#import<iostream>
long N,M,K,P,s=1,x,n;main(){std::cin>>N>>K>>M>>P;x=K-2,n=M;for(;x;x/=2,n=n*n%P)if(x&1)s=s*n%P;std::cout<<s*(N%P*M%P-(M+1)*M/2%P*(K-1)%P+P)%P;}

题解

设序列为 $a_1, a_2, \ldots, a_K$，满足 $1 \le a_1 < a_2 < \cdots < a_K \le N$ 且相邻差值 $d_i = a_i - a_{i-1}$（$i \ge 2$）都不超过 $M$。对任意一组差值序列 $(d_2,\ldots,d_K)$，如果把它们的和记为 $S$，则 $a_K = a_1 + S$。由于 $S \le M (K-1) < N$，总能选出合法的 $a_1$，且 $a_1$ 可以取 $1 \sim N - S$ 的任意整数。因此对于固定的差值组合，合法序列的数量恰为 $N - S$。

所有差值相互独立，且每个 $d_i$ 有 $M$ 种取值，所以共有 $M^{K-1}$ 组差值序列。于是答案为

$$\sum (N - S) = N \cdot M^{K-1} - \sum S.$$

而 $\sum S$ 可以拆分：每个位置的差值在所有组合中出现 $M^{K-2}$ 次，差值取值之和为 $\frac{M(M+1)}{2}$，一共有 $K-1$ 个位置，因而

$$\sum S = (K-1) \cdot M^{K-2} \cdot \frac{M(M+1)}{2}. $$

把上述公式整理后再对模数 $P$ 取模即可。代码中使用快速幂求出 $M^{K-2}$，再套用推导出的闭式公式。

#include <iostream>

int main() {
    long long N, M, K, P;
    std::cin >> N >> K >> M >> P;
    
    long long s = 1, x = K - 2, n = M;
    for (; x; x /= 2, n = n * n % P)
        if (x & 1)
            s = s * n % P;
    
    std::cout << s * (N % P * M % P - (M + 1) * M / 2 % P * (K - 1) % P + P) % P << '\n';
    return 0;
}