首页 > 其他 > 详细

CSPS模拟测试 43

时间:2019-09-15 23:05:09      阅读:89      评论:0      收藏:0      [点我收藏+]

  我这次把考试题改完了

  

  T1 A

  发现S*b必须和T模a同余?

  貌似乘不了几次就爆T了?可以暴力?

  也许乘的越多越好?

  内心:切了

  另外怎么设置鼠标指到黑块上边就显示字那种东西

  最后当然是因为低错没有A掉啦

  虽然思路不对但是测试数据没有卡啦

  反例:1 80 2 2

  std:6 ((1+2+2)*2*2*2*2)

  wrong:7((1*2*2*2+2)*2*2*2)

  当S很小的时候,加法可能比乘法增长的更快,更快接近T

 

  T2 B

  一边颓废骚扰天皇一边努力地证出了题解(本来想证那个引理)

  我要证明那个引理,只需说明每个点对下一层gcd(i,p)相等的i的贡献都相同

 

  首先对于gcd(i,p)==k的i,它能转移到的点j满足k|gcd(j,p)

  暂且把这些点抽离出来变成p/k个点,那么i的位置变成了i/k

  暂且讨论模p/k意义下的结果,(反正其他数也取不到,结果映射回去就行了

  可以知道i/k与p/k互质

  由于i/k要乘上0-p-1的每个数进行转移

  把这因数表示成 a*p/k+b

  由于乘法分配率,前一项相乘后模p/k为0,先忽略

  后一项,当b==0时,结果为0

  否则由于i/k与p/k互质,结果将取遍1-p/k-1的每一项

  把b当作循环变化,一共循环了k次

  即每个点对它能取到的点的方案数贡献是k

 

  故 每个点对下一层gcd(i,p)相等的i的贡献都相同 ,引理成立了

 

  猛然发现这样的点一共多少个呢,phi(p/k)(因为互质

  然后乘上每种类型点的数量,就从单点对单点变成了多点对单点(可以这样理解)

  状态转移方程出来了

 

  那么怎么想到那个规律呢

  如果脑子好使,你可以考场证明..

  那些得了高分的神犇们说是打表发现的..

 

  不能太懒,考试时打表说不定就有收获

 

  T3 C

  发现t是个单谷函数。

  三分,剩下的交给贪心。

  一个位置,能让前边顺便加热了就加热

  不得已时自己加热,同时尽量惠及后边的位置

CSPS模拟测试 43

原文:https://www.cnblogs.com/yxsplayxs/p/11524291.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!