写题中的技巧

这一篇博客分为两部分：

• 写代码
• 思路

我会将写题中所用到的一些想不到的又不至于单独写一篇博客的小trick放在这里。

写代码中用到的技巧

1. 有一种 $O(n)$ 求 $1~n$ 的逆元的方法：

1
2
3

ni[1] = 1;
_F(i,2,n)
	ni[i] = (p-p/i)*ni[mod%i]%mod;

写题中奇妙的思路（套路）

1. 区间 \[l,r] 在线段树上的区间定位数等于 $2×(r−l+1)−|S|$，其中 $∣S∣$ 表示线段树上包含于 \[l,r] 的区间个数。

2. 范围特别小$\leq 20$的时候一定要考虑状态压缩。

3. 对于一部份题目，可能先写出暴力会对正解有很大的帮助。

4. 当你想出了一个很像正解的结果并觉得有问题但是找不出时，相信他就是正解。

5. 对于一部份序列题，可以通过二分将原题转为 $01$ 序列题,再用好维护的数据结构进行维护。
   [P2824 [HEOI2016/TJOI2016] 排序](https://www.luogu.com.cn/problem/P2824)
   [[AGC006D] Median Pyramid Hard ](https://www.luogu.com.cn/problem/AT_agc006_d)

6. 动态规划本质上就是压缩有用的信息（dp维度）

7. $\max(a,b)<c$ 等价于 $a<c$ 且 $b<c$

8. $\max(a,b)>c$ 等价于 $a>c$ 或 $b>c$

9. 有一部分题目是行列可以分开做的，需要注意这样的东西。

10. $4444455555666667$ 是一个 long long 范围内的质数。

11. 拓扑排序可以进行反建图,很常用.

12. 有一部分的矩阵题可以行和列分开维护
    [P2258 [NOIP2014 普及组] 子矩阵 ](https://www.luogu.com.cn/problem/P2258)此题是将行 dfs 再将列 dp
    CF1202C You Are Given a WASD-string… 此题是将行列分开考虑,然后分别DP\前缀和
    CF1993E Xor-Grid Problem见blog
    C. Wonderful City行列分开DP

13. 对于一部分计树题，我们可以树->括号序->网格图计数，在对树深度有限制时特别好用。