【练习记录】之前的杂题整理(To Be Continued....)

主要是 CSP-S 2019 之前的杂题整理,天知道我为了整理这些东西要花费怎样漫长的时间去 read back 我的提交记录……


1、LG5317 花园

发现一共只有两种方格,并且转移只跟 $\rm M$ 有关,于是考虑状压。考虑 $g(s, t)$ 表示从状态 $s$ 转移到 $t$ 的方案数。其中转移指的是向右扩展一格。

那么显然这东西可以 dfs 预处理出来。然后发现这东西类似于 floyd 的转移矩阵,然后就快速幂。考虑由于花圃是个环,那么合法的方案就是 $1…m$ 和 $n+1….n+m$ 要相同。所以就直接把开头结尾相同的累加一波。

2、LG4218 完全平方数

一道傻题,大概就是考察 $\mu$ 的性质。

  • $\rm Algorithm~1$

    • 发现可以容斥,且 $\mu$ 函数的性质在于,$\mu (x) = (-1)^k$,当且仅当 $x$ 不含平方因子且 $x$ 的不同素因子个数为 $k$。所以就考虑先二分,二分完了求一下
      • 就变成傻题了。复杂度 $T \cdot \sqrt n \log n$

顺便记录一个很绝的 idea

  • $\rm Algorithm~2$

    • 根据 $\mu$ 的性质,发现似乎只有 $\mu(x) = 0$ 时,$x$ 才会被讨厌。所以其实二分求的就是

      • 然后我们发现这东西可以直接杜教筛。于是复杂度就变成了 $T\cdot n^{\frac{2}{3}} \log n$。然而实际记忆化了会更快。

但显然杜教筛被暴力给爆锤了好吗

3、[]