【BZOJ3142】[HNOI2013]数列

【BZOJ3142】[HNOI2013]数列

题面

洛谷
bzoj

题解

设第(i)天的股价为(a_i)，记差分数组(c_i=a_{i+1}-a_i)

则

[Ans=sum_{c_1=1}^Msum_{c_2=1}^Msum_{c_3=1}^M...sum_{c_{k-1}=1}^M(N-sum_{i=1}^{k-1}c_i)\ =N*M^{k-1}-sum_{c_1=1}^Msum_{c_2=1}^Msum_{c_3=1}^M...sum_{c_{k-1}=1}^Msum_{i=1}^{k-1}c_i\ =N*M^{k-1}-sum_{i=1}^{k-1}sum_{c_1=1}^Msum_{c_2=1}^Msum_{c_3=1}^M...sum_{c_{k-1}=1}^Mc_i\ =N*M^{k-1}-sum_{i=1}^{k-1}sum_{c_i=1}^M c_i*M^{k-2}\ =N*M^{k-1}-(k-1)*M^{k-2}*frac {(1+M)*M}2 ]

此题完结。

代码

#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <cmath> 
#include <algorithm> 
using namespace std;
typedef long long ll; 
ll N, K, M, Mod;
ll fpow(ll x, ll y) { 
	ll res = 1; 
	while (y) {
		if (y & 1ll) res = res * x % Mod; 
		x = x * x % Mod; 
		y >>= 1ll; 
	}
	return res; 
} 
int main () { 
#ifndef ONLINE_JUDGE 
    freopen("cpp.in", "r", stdin); 
#endif
	cin >> N >> K >> M >> Mod;
	N %= Mod, --K; 
	cout << ((N * fpow(M, K) % Mod - K * fpow(M, K - 1) % Mod * (M * (M + 1) / 2 % Mod) % Mod) % Mod + Mod) % Mod << endl; 
    return 0; 
}