[HNOI2013]數(shù)列

problem

洛谷鏈接

solution

假設(shè)每天的股價(jià)為 $a[i]$。則需滿足 ${?}_{i<k}a[i+1]?a[i]\le m$。又有參數(shù)滿足 $m(k?1)<n$。

也就是說(shuō)每天的股價(jià)都可以取到上限，即 ${?}_{i<k}a[i+1]?a[i]=m$。

當(dāng)然都要保證 $a[k]\le n$。

這種每天都有增長(zhǎng)求方案數(shù)的題目，容易聯(lián)想到差分。因?yàn)楫?dāng)差分?jǐn)?shù)組確定時(shí)，就只與第一個(gè)元素的值有關(guān)了。

用差分刻畫(huà)數(shù)組 是很經(jīng)典的套路。

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

一個(gè)差分?jǐn)?shù)組貢獻(xiàn)都是 $1$。但是有若干種股價(jià)方案的差分?jǐn)?shù)組是同一個(gè)，就可以合并計(jì)算。

這里可以采用對(duì)第一天股價(jià)的起始值刻畫(huà)出差分的增值一樣但本質(zhì)不同的股價(jià)方案。

顯然，方案數(shù)為 $n?{\sum }_{i=1}^{k?1}s[i]$。因?yàn)樵?$a[1]\in [1,n?{\sum }_{i=1}^{k?1}s[i]]$ 的時(shí)候，都有 $a[k]\le n$。

而本質(zhì)不同的差分?jǐn)?shù)列的個(gè)數(shù)又為 $m^{k?1}$，前面說(shuō)過(guò)任何一天的增值都有可能取到 $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$ 是將所有可能的合法差分?jǐn)?shù)列都計(jì)算到了。并且有 $s_j[i]\in [1,m]$。

先不管差分?jǐn)?shù)值，那么后面一共就會(huì)有 $m^{k?1}(k?1)$ 個(gè)數(shù)，并且在 $[1,m]$ 是均勻分布。

所以 $[1,m]$ 中的每個(gè)數(shù)出現(xiàn)次數(shù)都是一樣的，即 $m^{k?2}(k?1)$。在乘上數(shù)值即可。

$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)$。

后面的式子就是個(gè)等差數(shù)列求和而已。

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

有的題解覺(jué)得這個(gè)除法有點(diǎn)坑，有的用了 exgcd 求解逆元。

根本沒(méi)有這種必要啊？！

逆元是因?yàn)椴荒苷圆旁?$p$ 域內(nèi)去找有相同效果的數(shù)。

但是明顯 $m(m+1)$ 一定有一個(gè)是偶數(shù)，一定能被 $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; }

總結(jié)

以上是生活随笔為你收集整理的[HNOI2013]数列（差分）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。