csps模拟测试67

　　T1：%%%%BARCA考场怒切。

　　联赛数学题不是很常见。

　　$a+b<=n$且$(a+b)|ab$

　　既然要简化问题就要让他们除以gcd(a,b)以后互质

　　于是有了$(a'+b')*d|a'b'd^2$

　　同时约掉一个d$(a'+b')|a'b'd$

　　这是要有一个结论才能达到我们最终的目的。

　　由$gcd(a',b')=1$得到$gcd(a'+b',a'(b'))=1$得到$gcd(a'+b',a'b')=1$

　　所以$(a'+b')|d$，其实这是最终想要的，

　　因为一开始的$(a'+b')*d=a+b$所以这样就可以设$k(a'+b')=d$

　　然后通过不等关系得到$k(a'+b')^2=a+b<=n$出了平方就有根号复杂度了。

　　考虑枚举每个$i=(a'+b')$然后就可以得到$k=frac{n}{i^2}$个解，然后在考虑内部$a'b'$有多少对，仍然用辗转相除可以得到是欧拉函数。

　　$sum limits_{i=1}^{sqrt{n}} frac{n}{i^2} phi{(i)}$

　　T2：SB题 $O(nlogn)$求最长上升子序列。随便优化

　　T3：好题，如何考虑性质。

　　既然是斐波那契数肯定和斐波那契数列有关。而且构树方法很有规律，也就是说这棵树和子树长得一样

　　找一找那个和斐波那契有关，手画一下发现，对于一颗以黑点为根的树，其中距离根为i的白点的个数是斐波那契，

　　考虑这个东西进行转移并计数

　　设$f[i][0/1]$表示根为白点，距离根为i的白/黑点个数。$g[i]$表示根为黑点，距离根为i的白点个数。

　　ps：（dp定义利用了原树与子树的相同，所以不用确定根）

　　首先分类，对于具有相似性的一类一起统计，首先两个白点在一条祖先链上。

　　那么就可以得到，$sum limits_{i=1}^{n-1} f[i]sum limits_{j=0}^{n-i+1} f[j]$、

　　就是枚举距离(i)，再枚举位置(j) 理解的时候注意根不是定的，但是对于任意一个根只要颜色相同，我需要的方案数就一样。

　　然后两个白点不再某一个的祖先链上，那么一定以黑点为LCA

　　这时候$f[i][1]$的意义就明了了，仍然是枚举长度，然后枚举位置，

　　$sum limits_{i=1}^{2n} sum limits_{k=1}^{i-1} g[i-k-1]*f[k-1] sum limits_{j=1}^{n-2-max(i-k-1,k-1)} f[j][1]$