首页 > 其他 > 详细

数列题解,上古文章搬运

时间:2020-08-02 18:13:55      阅读:30      评论:0      收藏:0      [点我收藏+]

标签:是个   地址   -a   sum   不知道   can   

为什么小编会想要写这篇题解呢,小编也不知道

** 网上题解平均行数不超过5行

呃,这题代码极短,6行即可(逃

OJ中此题地址

#include<iostream>
#define ll long long
using namespace std;
ll n,m,k,p;
ll ksm(ll x,ll k){ll tmp=1;while(k){if(k&1)tmp=tmp*x%p;x=x*x%p,k/=2;}return tmp;}
int main(){scanf("%lld%lld%lld%lld",&n,&k,&m,&p),n%=p,m%=p,cout<<(ksm(m,k-1)*n%p-(((m+1)*m/2)%p*ksm(m,k-2)%p*(k-1)%p)%p+p)%p;}

但是如果思路被带偏了,就会像小编一样想了两个小时才理解
首先考虑“构造”出一个合法的 \(a\) 数组,用以记录每天股票的价格
那么根据题意 \(a[i]-a[i-1]<=m\) ,题目中又写到 \(m*(k-1)< n\) ,那么就算每一个 \(a[i]\) 都取到 \(a[i]==a[i-1]+m\) 也没问题
现在再构造一个差分数组 \(b\) 也就是定义 \(b[i]=a[i]-a[i-1]\) ,那么 \(b[i]<=m\) ,那么不考虑“最高价格不超过n” \(ans=m^{k-1} * (a[1]的可能取值)\)
\(m^{k-1}\) 的意思就是,每个 \(b[i]\) 都可以从 1 到 \(m\) 随便取一个值,这就是个乘法原理,不解释下去了(不然反而看不懂)
那么我们来想想 \(a[1]\) 的取值
hin显然,

\[a[1]=n-\sum_{x=1}^{n}{b_x} \]

那么

\[ans=m^{k-1}*(n-∑b_x)=n*m^{k-1}-∑∑b_x \]

为什么拆括号的时候会有这个奇怪问题呢,因为前面 \(m^{k-1}\) 是会影响 \(b_x\)
毕竟 \(m^{k-1}\) 是一个方案数,并没有考虑方案不同而导致的不同结果
\(∑∑b_x\) 可以转化为一个数在差分序列中出现的次数,用

\[(k-1)*m^{k-2}*(m+1)*m/2 \]

计算
因为 \(b_x\) 的数值是在 1 到 \(m\) 中随便选取的,那么显然一个数可以在 \((k-1)\) (每)个位置都出现一次,然后其他 \((k-2)\) 个数值可以随便选取
然后等差数列求和就完了(我 * * 这里想了贼久,其实就是每个数字是有实际贡献的,hhhc)
接下来请大家多多提问,让这题思路更完整更清晰(方俊豪打爆电话警告),补丁列表:

为什么要乘上等差序列求和呢:请注意-∑∑bx前面((k-1)*m^k-2)算出来的是每个数出现的次数,但是我们要算的是-∑∑bx所以根据“总价=数量*单价”,需要乘上∑i

另外安利一下一位大佬 \(broxin\) ,他的数列题解是百度上最详细的

数列题解,上古文章搬运

标签:是个   地址   -a   sum   不知道   can   

原文:https://www.cnblogs.com/caijiLYC/p/13419751.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号