找规律从入门到入土
WYXkk
·
2020-10-29 18:30:26
·
算法·理论
提前提醒：本文提到的所有题目中的结论均没有证明，因为本文就是在找规律。
众所周知，在写题目的时候，找规律，是一项非常有用的技能。
如果你成功找到了题目中的数列等的规律，那么便可以大大简化代码甚至吊打std。
接下来我们介绍几个找规律的方法及例题。
0.前置芝士
要想找规律，先得会写暴力。暴力的时空复杂度不要过于离谱（例如 O((n!)^2)）都可以接受。
有些题目的答案是分数，并且输出时对大质数取模。
对小数找规律和对取模后结果找规律都不现实，所以我们得写个分数类。
分数类至少得支持加减乘除，比较可以写上，转实数也可以写上。
给个我的分数类板子（写的可能不是很好
1.基础操作
例题：P6026，k=2
给定正整数 n，在 [1,n] 中等概率随机一个正整数 r_1，在 [1,r_1] 中等概率随机生成一个正整数 l_1，同理生成 l_2,r_2，求 [l_1,r_1]\cap[l_2,r_2]=\varnothing 的概率。n\le10^6。
式子推不出来，那么就找规律吧，于是我们先写个 O(n^4) 大暴力：（伪代码）
ans=0;
for(l1=1->n) for(r1=1->n) for(l2=1->n) for(r2=1->n)
if(l2>r1||l1>r2) ans+=1/(n*n*r1*r2);
print(ans);
暴力敲出来后跑一下，发现前几项大概是这样的：0/1,1/4,1/3,3/8,2/5,5/12,3/7,\cdots
似乎规律不大？
但是事实上是我们约分过度了，可以发现前几项是：0/2,1/4,2/6,3/8,4/10,5/12,\cdots
应 happydef 要求，说下这个反约分是怎么来的：
通项公式应该很简洁，我们认为它是 \dfrac{P(n)}{Q(n)} 的形式，其中 P,Q 为两个多项式。
带有特判的通项都是不好的，应该有 P(1)=0 从而 x-1|P(x)。
然后我们就会试图把分子弄成尽量靠近这种形式，所以就如此反约分。
然后答案不就出来了吗：\dfrac{n-1}{2n}。
这个弱化是我做的某场比赛里的题，然后 std 是奇怪的 O(n) 递推，于是我吊打了 std？（
例题：P6026
给定正整数 n，在 [1,n] 中等概率随机一个正整数 r_1，在 [1,r_1] 中等概率随机生成一个正整数 l_1，同理生成 l_2,r_2,\cdots,l_k,r_k，求 \forall i\neq j[l_i,r_i]\cap[l_j,r_j]=\varnothing的概率。
我们继续类似找规律，写个 O(k^2n^{2k}) 的大暴力（dfs+两两判断），然后进过一系列的找规律可以发现 k=3 时规律是 \dfrac{(n-1)(n-2)}{6n^2}，k=4 时规律是 \dfrac{(n-1)(n-2)(n-3)}{24n^3}，等等。
和上面说的一样，因为 n 然后我们对这些规律结果找规律，可以发现答案即为 \dfrac{C_n^k}{n^k}。 2.差分 例题：P6042 给定 n，求\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j(\min(i-j,j-k))! 写个 O(n^3) 大暴力：（伪代码） jc[0]=1,ans=0;for(i=1->n)jc[i]=jc[i-1]*i; for(i=1->n)for(j=1->i)for(k=1->j)ans+=jc[min(i-j,j-k)]; print(ans); 然后我们看看结果：1,4,10,20,36,60,98,156,258,428,786,1452,\cdots 似乎没什么规律，那么我们差分：1,3,6,10,16,24,38,58,102,170,358,666,\cdots 似乎仍然没有规律，那么我们继续差分：1,2,3,4,6,8,14,20,44,68,188,308,\cdots 貌似有点规律了，我们最后差分一次：1,1,1,1,2,2,6,6,24,24,120,120,\cdots 于是我们得出结论，差分三次后就是将阶乘数列每个数复读一遍的数列。 那么预处理阶乘，得出三阶差分数列，然后前缀和三次，每个询问直接输出，做完了。 3.注意一些特殊序列 例题：P6043 一场比赛两道找规律？ 给定 n,m 求 \sum_{i=0}^m \lgroup \frac{\sqrt{\sum_{j=0}^i (C_i^j)^2C_{n+2i-j}^{2i}}}{\Gamma(n+1,n+i)} \times \Gamma(n-i+1,n) \rgroup 其中 \Gamma(a,b) 定义为 a 到 b 的连乘积，即 \Gamma(a,b)=\left\{\begin{aligned}& 1,a>b&\\& \prod_{i=a}^b i,a \le b&\\\end{aligned}\right. 这个式子看起来就很不可做，所以我们可以写个暴力找规律看看。 至于暴力写法，直接预处理阶乘然后算组合数和 \Gamma 就好了。 暴力出来大概是这个样子（(n,m) 的答案在 n 行 m 列） 2 3 4 4 7 8 5 11 15 16 6 16 26 31 32 7 22 42 57 63 64 似乎没啥规律啊？ 但是如果我们差分一下，就会发现它变成了杨辉三角。 那么题目就变成了 \sum_{i=0}^mC_n^i，至少让我从只会暴力变成了会 O(n) 部分分，多了整整20分。 题外话：我比赛时做到这些后就去BaiduFirstSearch组合数前缀和，在LOJ上搜到了，本来想嫖某神仙的代码然后发现他已经过了这题遂取消并与他谈笑风生 例题：CF1327E（题目难描述自己看） 样例给的没啥规律，我们自己写个暴力找吧。 直接dfs所有 n 位数，写出表达，暴力计算，完事。 得到的答案是这样的 1:10 2:180 10 3:2610 180 10 4:34200 2610 180 10 5:423000 34200 2610 180 10 6:5040000 423000 34200 2610 180 10 7:58500000 5040000 423000 34200 2610 180 10 8:666000000 58500000 5040000 423000 34200 2610 180 10 我们发现 n+1 的答案就是 n 的答案在前面加一个数。从而 n 的答案就是某个序列的前 n 项反过来。 我们把除第一项外的去掉结尾若干个 0 可以得到 180,261,342,504,585,666，是一个等差数列。 根据这两个规律就可以做了。 似乎这还是道 OEIS 题？ 4.如何写暴力 有些题挑明了是找规律，但是暴力不好写。 例题：P6130（题目自己看） 实随机？这就有点难受了啊。 但是我们可以用整随机逼近，即 rand(1,N)/N 这种。 可以多随机几次求平均，也可以直接枚举所有情况求平均。 然后发挥适当的想象（？）就可以找到规律。 具体见我的题解。 例题：CF1329B（题目太长了自己看） 这个序列如何枚举是一个问题。 事实上我们可以直接 dfs。dfs 时记录目前的 a_i,b_i，随后枚举比 a_i 大的 a_{i+1}，如果得到的 b_{i+1} 比 b_i 大则继续 dfs 下去。 之后使用差分即可找到规律，详见我的题解。 5.其他找规律 例题：P6435（自己看） emm 暴力似乎不太行，我们推前几个式子然后找式子的规律？ 事实证明这是可以的，详见我的题解 找规律也有对式子找规律哦。 例题：P6196 我们可以先写暴力并记录结果的操作序列，然后对操作序列找规律。 就是，看看操作序列大致是怎样来的。 暴力可以使用双向链表模拟删除和撤销删除。 然后就能大致看出一些东西了。详见我的题解 找规律也能对操作方法找规律。 6.注意找规律对象 例题：P6608 首先作一些很 trival 的处理，可以反过来操作。 如果你对结果序列找规律，那么就会当场暴毙（比如赛时的我）。 我们应该对每次的操作对象找规律。这样就能找到规律过掉。 具体见 我的题解 7.附录 找规律，是一种考场技巧。建议大家在平时做题时，即使找到并找对规律并做了出来，也在 AC 后去题解区等看规律的证明。 找规律 AC 肯定是好的，但是也不能忽视推式子的能力。 这么做，能让你在即使找不到规律时也能想办法推出式子来。 有真的能找规律的好题欢迎投稿，本文随时更新。 点名 @Karry5307 别给我推 P6073 完结撒花！