[HNOI 2013]数列

Description

题库链接

给你四个数 (N,K,M,P) ，让你生成一段长度为 (K) 严格单调递增序列，并且满足：

1. 第一位可以为任意元素；
2. 相邻两位的差值不超过 (M) ；
3. 序列中元素大小不超过 (N) 。

求满足上述要求不同的生成序列有多少个，对 (P) 取模。

(1leq Nleq 10^{18},1leq K,M,Pleq 10^9)

Solution

其实容易发现，我们可以生成长度为 (K) 以增量为元素的序列 (A) 。

等价的变成了：

1. 第一位可以为任意元素；
2. 其余元素 (in [1,M]) ；
3. (sumlimits_{i=1}^K A_ileq N) 。

我们先不考虑第一位元素的选取情况。其余 (K-1) 个元素选取情况为 (M^{K-1}) 。那么对于每种生成序列 (A) ，它第一位可以选的元素 (inleft[1,N-sumlimits_{i=2}^KA_i ight]) 。

容易发现，每种 ([2,K]) 位生成序列第一位的情况有 (N-sumlimits_{i=2}^KA_i) 种。记所有 (2sim K) 位生成排列的集合为 (mathbb{S}) 我们枚举生成的排列。那么答案为：[sum_{sinmathbb{S}}left(N-sumlimits_{i=2}^KA_i ight)]

等价变形为： [egin{aligned}&NM^{K-1}-sum_{sinmathbb{S}}sumlimits_{i=2}^KA_i\=&NM^{K-1}-(K-1)frac{1+2+cdots+M}{2}M^{K-2}\=&NM^{K-1}-(K-1)frac{(M+1)M}{2}M^{K-2}end{aligned}]

直接求解即可。

Code

//It is made by Awson on 2018.3.10
#include <bits/stdc++.h>
#define LL long long
#define dob complex<double>
#define Abs(a) ((a) < 0 ? (-(a)) : (a))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
#define writeln(x) (write(x), putchar('
'))
#define lowbit(x) ((x)&(-(x)))
using namespace std;
void read(LL &x) {
    char ch; bool flag = 0;
    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
    x *= 1-2*flag;
}
void print(LL x) {if (x > 9) print(x/10); putchar(x%10+48); }
void write(LL x) {if (x < 0) putchar('-'); print(Abs(x)); }

LL n, k, m, p, ans, t;

LL quick_pow(LL a, LL b) {
    LL ans = 1;
    while (b) {
    if (b&1) ans = ans*a%p;
    a = a*a%p, b >>= 1;
    }
    return ans;
}
void work() {
    read(n), read(k), read(m), read(p); n %= p;
    ans = n*quick_pow(m, k-1);
    if (m&1) t = (m+1)/2*m%p; else t = m/2*(m+1)%p;
    ans = (ans-(k-1)*t%p*quick_pow(m, k-2)%p)%p;
    writeln((ans+p)%p);
}
int main() {
    work(); return 0;
}