【BZOJ3142】[HNOI2013]数列

题面

洛谷

bzoj

题解

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

则

\[Ans=\sum_{c_1=1}^M\sum_{c_2=1}^M\sum_{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}^M\sum_{c_2=1}^M\sum_{c_3=1}^M…\sum_{c_{k-1}=1}^M\sum_{i=1}^{k-1}c_i\\
=N*M^{k-1}-\sum_{i=1}^{k-1}\sum_{c_1=1}^M\sum_{c_2=1}^M\sum_{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;
}