[数据结构与算法][HNOI2013]数列（差分）

[HNOI2013]数列

problem

洛谷链接

solution

假设每天的股价为 $a[i]$。则需满足 ${?}_{i<k}a[i+1]?a[i]\le m$。又有参数满足 $m(k?1)<n$。

也就是说每天的股价都可以取到上限，即 ${?}_{i<k}a[i+1]?a[i]=m$。

当然都要保证 $a[k]\le n$。

这种每天都有增长求方案数的题目，容易联想到差分。因为当差分数组确定时，就只与第一个元素的值有关了。

用差分刻画数组 是很经典的套路。

令 ${?}_{i<k}s[i]=a[i+1]?a[i]$。

一个差分数组贡献都是 $1$。但是有若干种股价方案的差分数组是同一个，就可以合并计算。

这里可以采用对第一天股价的起始值刻画出差分的增值一样但本质不同的股价方案。

显然，方案数为 $n?{\sum }_{i=1}^{k?1}s[i]$。因为在 $a[1]\in [1,n?{\sum }_{i=1}^{k?1}s[i]]$ 的时候，都有 $a[k]\le n$。

而本质不同的差分数列的个数又为 $m^{k?1}$，前面说过任何一天的增值都有可能取到 $m$。

综上可以得出答案的式子：${\sum }_{j=1}^{m^{k?1}}(n?{\sum }_{i=1}^{k?1}{s}_j[i])=n{m}^{k?1}?{\sum }_{j=1}^{m^{k?1}}{\sum }_{i=1}^{k?1}{s}_j[i]$。

显然 $s$ 是将所有可能的合法差分数列都计算到了。并且有 $s_j[i]\in [1,m]$。

先不管差分数值，那么后面一共就会有 $m^{k?1}(k?1)$ 个数，并且在 $[1,m]$ 是均匀分布。

所以 $[1,m]$ 中的每个数出现次数都是一样的，即 $m^{k?2}(k?1)$。在乘上数值即可。

$ans=n{m}^{k?1}?{\sum }_{j=1}^{m^{k?1}}{\sum }_{i=1}^{k?1}{s}_j[i]=n{m}^{k?1}?{\sum }_{i=1}^{m}i?m^{k?2}(k?1)$。

后面的式子就是个等差数列求和而已。

最后化简答案：$ans=n{m}^{k?1}?\frac{(m+1)m}{2}{m}^{k?2}(k?1)$。

有的题解觉得这个除法有点坑，有的用了 exgcd 求解逆元。

根本没有这种必要啊？！

逆元是因为不能整除所以才在 $p$ 域内去找有相同效果的数。

但是明显 $m(m+1)$ 一定有一个是偶数，一定能被 $2$ 整除。

code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, k, p;

int qkpow( int x, int y ) {
    int ans = 1;
    while( y ) {
        if( y & 1 ) ans = ans * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return ans;
}

signed main() {
    scanf( "%lld %lld %lld %lld", &n, &k, &m, &p );
    printf( "%lld\n", ( n % p * qkpow(m, k - 1) % p - qkpow(m, k - 2) * (k - 1) % p * (m * (m + 1) / 2 % p) % p + p ) % p );
    return 0;
}