CSPS模拟 57

　　rank4大众rank

　　T1 天空龙

　　　　让他自由翱翔吧

　　T2 巨神兵

　　　　对于n=10的测试点本可以打出非常优秀的分层状压

　　　　但是没有打出来，因为对拓扑图理解不够深刻，纠结于指回的边，实际上只关注伸出的边就可以

　　　　正解则是跟分层一点关系都没有

　　　　记录两层的状态一定要gg的，所以只记录一层

　　　　那么状态定义就不可避免地成了”保证状态是个拓扑图“

　　　　然后内部一片混沌，于是又得容斥。

　　　　假设现在我们有一个完全正确的状态$st$，也就是所有符合条件的状态都被计算一次

　　　　考虑如何转移到更庞大的一个状态$state$

　　　　由于$dp$是枚举所有状态和所有转移，所以我们可以认为$st -> state$的过程会经过所有可能的路径

　　　　将这些路径分类来达到容斥的目的

　　　　假设$size[state^st]=sz$

　　　　那么根据最后一次加入点的个数可以分成：

　　　　$1 C_{sz}^1 条$

　　　　$2 C_{sz}^2 条$

　　　　${sz} C_{sz}^{sz}条$

　　　　这种组合数的东西，我们十分套路地使用奇加偶减就行了

　　　　具体来说就是转移的时候，如果加入奇数个点则系数为1，否则系数为-1

　　　　枚举最大公约数，则$ans=\sum \limits_d=1^n \sum \limits_{1<=a,b<=\frac{n}{d}} [gcd(a,b)==1]$

　　　　而$n/d$只有$\sqrt[2]{n}$种取值，所以先上分块

　　　　随后的东西我不会证复杂度了

　　　　$sol1$

　　　　假设a<b枚举$a<\sqrt[2]{\frac{n}{d}}$,变成$\sum\limits_{a=1}^{\frac{n}{d}} [gcd(a,\frac{n}{d*a})==1]$

　　　　设$k=frac{n}{d}$，上莫比乌斯反演$\sum\limits_{a=1}^k \sum\limits_{t|a} u(t)$

　　　　$\sum\limits_{t=1}^k u(t) \sum\limits_{x=1}^{x*t<=k} 1 -phi(x*t)$

　　　　然后直接就是调和级数，时间复杂度$nlogn$，空间复杂度根号

　　　　可以水到80

　　　　$sol2$

　　　　考虑函数$f(x)=\sum\limits_{1<=a,b<=k} [a*b<=k][gcd(a,b)==1]$

　　　　发现$f(x)$比$f(x-1)$多出的部分就是$\sum[a*b==k][gcd(a,b)==1]$

　　　　也就是把k拆成两部分，不含有相同的质因子

　　　　$delta=2^{d(k)}$

　　　　可以线筛，时间复杂度$n$,空间复杂度$n$

　　　　如果你能结合$sol1,sol2$，同时计算出最优复杂度分界线$n^{\frac{2}{3}}$，可以直接AC

　　　　$sol3$

　　　　还是考虑那个函数，这次上容斥（又是容斥，算上明天的题都3道容斥题了）

　　　　设$g(i)=\sum\limits_{1<=a,b<=k} [a*b<=k]$

　　　　枚举ab的gcd t，则重复的部分就是k中除去$t^2$之后分成两个互质的数的方案数

　　　　这不就是f自己

　　　　$f(i)=g(i)-\sum\limits_{t>1} f(\frac{k}{t^2})$

　　　　递归调用自己，复杂度不会证，听说是$n^{\frac{2}{3}}$

　　　　然后又要玄学计算最优复杂度分界线又是$n^{\frac{2}{3}}$，结合sol1可以用更快的速度AC

　　恰完饭再写，饿。

巴特西

CSPS模拟 57

最新文章

热门文章