bzoj千题计划293:bzoj3142: [Hnoi2013]数列
2024-10-15 09:13:04
http://www.lydsy.com/JudgeOnline/problem.php?id=3142
如果已知数列的差分数列a[1]~a[k-1]
那么这种差分方式对答案的贡献为 N-Σ a[i],i∈[1,k-1]
差分数列一共有多少种? M^(k-1) 种
所以ans=Σ (N-Σa[i]) = M^(k-1) * N - Σ Σ a[i] = M^(k-1) *N-(k-1)*M^(k-1) /M * (M+1)*M/2
后面是因为一共 M个数 出现(k-1)*M^(k-1) 次,每个数出现的次数相同
所以每个数出现 (k-1)*M^(k-1) / M 次
(M+1)*M/2 是所有的数各出现一次的和
没做出来的原因:没有展开Σ,没有考虑每个数的出现次数相同
#include<cstdio> using namespace std; typedef long long LL; LL Pow(LL a,LL b,LL p)
{
LL res=;
for(;b;a=a*a%p,b>>=)
if(b&) res=res*a%p;
return res;
} int main()
{
LL n,k,m,p;
scanf("%lld%lld%lld%lld",&n,&k,&m,&p);
printf("%lld",(n%p*Pow(m,k-,p)%p-(k-)*Pow(m,k-,p)%p*(m*(m+)/%p)%p+p)%p);
}
最新文章
- 译文---C#堆VS栈(Part One)
- 如何获取ios 设备名字 model
- C++实现二叉树,运用模板,界面友好,操作方便 运行流畅
- SQL Server实现数据的递归查询
- [GIF] Parenting in GIF Loop Coder
- Java工作队列和线程池
- ext 金额大写
- linux 网络Socket实战
- C#实现局域网内远程开机
- Python字符串和日期相互转换的方法
- Windows上MongoDB的安装
- 201421123042 《Java程序设计》第5周学习总结
- Java 去掉字符串中的换行符回车符等
- 初学python之路-day03
- linux学习:文件处理相关命令用法整理(正则表达式)
- 四层和七层负载均衡的特点及常用负载均衡Nginx、Haproxy、LVS对比
- 适配手机端之 rem
- 跨域导致无法获取cookie
- SSIS组件——Merge、Merge Join、Union All
- 微信、支付宝App支付-JPay0.0.2发布
热门文章
- Easy Pipeline,一种轻量级的Python Pipeline库
- 【ORACLE】Win2008R2修改oracle数据库实例名
- 如何解决markdown中图片上传的问题
- muduo网络库学习笔记(五) 链接器Connector与监听器Acceptor
- Scrum Meeting day 2
- LINUX内核分析第五周学习总结——扒开应用系统的三层皮(下)
- Ubuntu读取/root/.profile时发现错误:mesg:ttyname fa
- [转帖]LNMP组件安装
- FuelPHP 系列(三) ------ Model 模型
- Ubuntu17安装maven3.5.2