小T最近在学着买股票,他得到内部消息:F公司的股票将会疯涨。股票每天的价格已知是正整数,并且由于客观上的原因,最多只能为N。在疯涨的K天中小T观察到:除第一天外每天的股价都比前一天高,且高出的价格(即当天的股价与前一天的股价之差)不会超过M,M为正整数。并且这些参数满足M(K-1)<N。 小T忘记了这K天每天的具体股价了,他现在想知道这K天的股价有多少种可能
【bzoj3142】【HNOI2013】【数列】【数学】
发布日期:2021-11-16 15:38:09
浏览次数:30
分类:技术文章
本文共 1050 字,大约阅读时间需要 3 分钟。
Description
Input
只有一行用空格隔开的四个数:N、K、M、P。对P的说明参见后面“输出格式”中对P的解释。 输入保证20%的数据M,N,K,P≤20000,保证100%的数据M,K,P≤109,N≤1018 。
Output
仅包含一个数,表示这K天的股价的可能种数对于P的模值。【输入输出样例】
Sample Input
7 3 2 997
Sample Output
16
【样例解释】
输出样例的16表示输入样例的股价有16种可能:
{1,2,3},{1,2,4},{1,3,4},{1,3,5}, {2,3,4},{2,3,5},{2,4,5},{2,4,6}, {3,4,5},{3,4,6},{3,5,6},{3,5,7},{4,5,6},{4,5,7},{4,6,7},{5,6,7}
【样例解释】
输出样例的16表示输入样例的股价有16种可能:
{1,2,3},{1,2,4},{1,3,4},{1,3,5}, {2,3,4},{2,3,5},{2,4,5},{2,4,6}, {3,4,5},{3,4,6},{3,5,6},{3,5,7},{4,5,6},{4,5,7},{4,6,7},{5,6,7}
题解:
对原序列差分。
那么对于一种确定差分,不同的方案在于首元素。
那么我们统计出所有的差分序列的和,用n*m^(k-1)减一下就是答案。
我们可以单独考虑每一个数,它的贡献就是m^(k-2)*m*(m+1)/2;
所以最后答案就是n*m^(k-1)-(k-1)*m^(k-1)*(m+1)/2
代码:
#include#include using namespace std;long long n,m,k,p,ans;long long power(long long a,long long b){ long long ans;a%=p; for (ans=1;b;a=a*a%p,b>>=1) if (b&1) ans=ans*a%p; return ans;}int main(){ scanf("%lld%lld%lld%lld",&n,&k,&m,&p); if (k==1) ans=n%p; else ans=(power(m,k-2)*(n%p*m%p-(m*(m+1)/2)%p*(k-1)%p+p)%p)%p; cout< <
转载地址:https://blog.csdn.net/sunshinezff/article/details/50923521 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月06日 02时50分49秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
JavaScript的事件响应与网页交互
2019-04-26
JavaScript实现的网页计算器功能
2019-04-26
英语四六级考试忘记准考证?怎么办?
2019-04-26
JavaScript内置对象
2019-04-26
JavaScript的游览器对象
2019-04-26
DOM对象,控制HTML对象
2019-04-26
制作一个表格,显示班级的学生信息
2019-04-26
JavaScript的选项卡操作
2019-04-26
Linux常用命令及文件处理命令
2019-04-26
Linux常见目录及作用
2019-04-26
文件链接命令
2019-04-26
Oracle篇--05 Oracle 视图、序列、约束
2019-04-26
【Java面试题四】sql面试题(1)
2019-04-26
【Java面试题五】sql面试题(2)
2019-04-26
【Java面试题六】多线程篇
2019-04-26
【Java面试题七】Java泛型篇
2019-04-26
【Java面试题八】Java算法优化篇
2019-04-26
JDBC与DAO篇--01 JDBC原理、JDBC基础编程
2019-04-26
【Java面试题九】算法篇
2019-04-26