在 AT_agc_005d 中，第一篇题解提到了一种建模方法，使得可以把很多排列计数问题转化将为一个 $n\times n$ 的网格图，划分为两类网格，暂且把其中一类成为特殊格子，求放置 $n$ 个互不攻击的狙，其中 $m$ 在特殊格子上的方案数。

类似的，CF285E 也可以这样做。

现在考虑几个加强版问题：

1. 可以看到题目中的特殊格子的位置是有特殊性质的，现在把性质弱化，可以举出以下问题作为例子：

如果一个排列 $P$ 满足对于所有的 $i$ 都有 $|P_i-i|\neq k_i$，则称排列 $P$ 为合法的。现给出 $n$ 和一个序列 $k_i$，求有多少种合法的排列。

也就是说，每行的两个特殊格子（不考虑只有一个的边界情况）距离不一定相等

2. 对此问题进一步加强，可以看到加强版问题还是有特殊性质的，现在有一个比较一般的问题：

定义一个 $1$ 到 $n$ 的排列 $P$ 的权值为，满足给定的 $k$ 个形如 $(a,b)$ 的关系，使得 $P_a =b$ 的个数，对于每个小于等于 $k$ 的非负整数 $x$ 求所有权值为 $x$ 的方案数。

这样就可以建立没有任何性质的网格图了。

关于没有性质，几个地方要注意一下，同行同列不一定有两个特殊网格，可能只有一个甚至可能没有，当然，也可以有超过两个特殊格子。

3. 其实上述问题仍然可以加强，发现网格图本身就是一个特殊性质，因为网格图是正方形的，还是上面问题，但我们把 $P$ 的定义改为一个 $1$ 到 $n$ 的排列的前 $m$ 个元素组成的序列，也就是说，对于这样的排列计数类问题，只考虑前面几个位置的方案数是否可做，即，是否有一个一个往序列末尾放入元素，而不是建图求独立集最大流之类的做法

4. 观察到这个问题本质上自带一个特殊性质，那就是互不攻击的狙，原因是因为排列，考虑对问题弱化然后加强，得到一个拓展问题：

弱化：

定义值域为一个 $1$ 到 $n$ 长度为 $m$ 的数组 $P$ 的权值为，满足给定的 $k$ 个形如 $(a,b)$ 的关系，使得 $P_a =b$ 的个数，对于每个小于等于 $k$ 的非负整数 $x$ 求所有权值为 $x$ 的方案数。

这个问题是好求的，我们假设行表示位置列表示值，虽然每行只能有一个，但列与列之间没有限制，是容易 $dp$ 的。

第一个加强：时空限制不变，数据范围 $n，m\le1e5，k\le1e6$ 即求一个低于平方的做法

第二个加强：在上述问题上加一个限制，给定一个数组 $a$ 得到以下 $4$ 个问题

1. 求给定每个数字 $i$ 的出现次数恰好为 $a_i$ 的方案数

2. 求给定每个数字 $i$ 的出现次数不小于 $a_i$ 的方案数

3. 求给定每个数字 $i$ 的出现次数不大于 $a_i$ 的方案数

4. 求给定每个数字 $i$ 的出现次数不为 $a_i$ 的方案数

类似的，我还能想到很多可以转换到网格图上的问题，无法一一列举，但似乎并不是每个问题都可做，现在问几个问题：

1. 不考虑利用多项式优化，只用基础的计数 dp，容斥等方法，怎样确定这样的问题的最优时间复杂度

2. 上述问题是否有一个统一的底层思路

3. 上面几个问题怎么做