HNOI2013 数列

题面

设第i天到第i+1天的涨幅为$a_i$,容易得到柿子:

$$Ans=\sum_{a_1=1}^m\sum_{a_2=1}^m\dots\sum_{a_{k-1}=1}^m(n-\sum_{i=1}^{k-1}a_i)$$

但是跑不过。

所以需要展开柿子:
$$
\begin{align}
Ans &= \sum_{a_1=1}^m\sum_{a_2=1}^m\dots\sum_{a_{k-1}=1}^m(n-\sum_{i=1}^{k-1}a_i)\\
&= nm^{k-1}-\sum_{a_1=1}^m\sum_{a_2=1}^m\dots\sum_{a_{k-1}=1}^m\sum_{i=1}^{k-1}a_i\\
&= nm^{k-1}-\sum_{i=1}^{k-1}\sum_{a_1=1}^m\sum_{a_2=1}^m\dots\sum_{a_{k-1}=1}^ma_i\\
&= nm^{k-1}-(k-1)m^{k-2}\sum_{i=1}^{m}i\\
&= nm^{k-1}-(k-1)m^{k-2}\frac{m(m+1)}{2}\\
\end{align}
$$

然后就是快速幂了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

ll fpm(ll a,ll b,ll p){
ll c=1;
while(b){
if(b&1)c=c*a%p;
a=a*a%p;
b>>=1;
}
return c;
}
int main(){
#ifdef cnyali_lk
freopen("3228.in","r",stdin);
freopen("3228.out","w",stdout);
#endif
ll n,m,k,p;
n=read();//read是读入
k=read()-1;
m=read();
p=read();
n%=p;
printf("%lld\n",(n*fpm(m,k,p)%p-fpm(m,k-1,p)*k%p*(m*(m+1)/2%p)%p+p)%p);
return 0;
}
文章目录
|

博客使用Disqus作为评论系统