【BZOJ 4373】算术天才⑨与等差数列

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4373
神犇题解:http://blog.csdn.net/TA201314/article/details/51177011

解题报告

首先,假如一个区间满足以下三个条件那么该区间一定合法:

$\%k$后相等
每一个数互不相同
区间和等于某一特定值

后两个条件都可以用线段树维护
问题就是第一个条件非常麻烦

先来考虑一种简单的Hash方式:记录区间的平方和
这样的话,我们可以$O(1)$计算基准值,$O(\log n)$判断是否等于基准值

但众所周知,Hash是不优雅的
于是我们可以先做一个差分序列,然后维护差分序列相邻两项的$\gcd$
考虑如果所有数的差都是$k$的整数倍,那么这些数$ \bmod \ k$之后肯定就相等啦!

另外的话,区间GCD配合差分的题,也不是第一次见了
之前NOI还考过一道:魔幻棋盘
以后和GCD相关的题目要想一想差分行不行啊!

18 thoughts to “【BZOJ 4373】算术天才⑨与等差数列”

  1. Thanks on your marvelous posting! I genuinely enjoyed reading it, you will be a great author.I will ensure that I bookmark your blog and definitely will come back at some point. I want to encourage you to definitely continue your great writing, have a nice day!

  2. 534721 681522Some times its a discomfort inside the ass to read what men and women wrote but this web web site is very user friendly ! . 502450

  3. 741137 517055Most heavy duty trailer hitches are designed utilizing cutting edge computer aided models and fatigue stress testing to ensure optimal strength. Share new discoveries along with your child and keep your child safe by purchasing the correct design for your lifestyle by following the Perfect Stroller Buyers Guideline. 24847

  4. I like what you guys are up too. Such clever work and reporting! Carry on the excellent works guys I¦ve incorporated you guys to my blogroll. I think it’ll improve the value of my website 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *