HNOI2013 数列

题面

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

但是跑不过。

所以需要展开柿子:

然后就是快速幂了。

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作为评论系统