（CSP2019模拟）DTOJ 4632. 隐蔽的居所

本文主要是介绍（CSP2019模拟）DTOJ 4632. 隐蔽的居所，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

在小G的家乡，有很多人住在一个大湖的边上。

他告诉小D，这个大湖可以被视作一个圆。一共有 $N$ 户人家，他们住在这个圆的 $N$ 等分点上，每个 $N$ 等分点上恰好有一户人家.

这里的每户人家都有不同的信仰，其中第 $i$ 户人家信仰第 $i$ 种宗教。很显然，宗教对于生活会产生一定的影响，具体来说，相邻两户人家信仰的宗教的编号之差的绝对值不可以超过 $K$ 。

同时，有几户人家会不满其他的一些人，对于两户人家 $i$ 和 $j$ ，如果 $i$ 不喜欢 $j$ ，那么 $j$ 不可以住在 $i$ 顺时针方向的下一个位置上，这样的不满关系一共有 $M$ 对。

小D突然好奇起来了，这 $N$ 户人家一共有多少种不同的居住方法呢?

小D的方向感不好，所以如果两种方案可以通过顺时针旋转某个角度变成一样的，那么小D就不会认为这两种方案不同。
对于所有数据,有 $\le N \le 10^6,0 \le M \le 10^5,0 \le K \le 3$

Subtask1 5%： $K = 0$

Subtask2 5%： $N = 1$

Subtask3 5%： $N = 2$

Subtask4 5%： $K = 1$

Subtask5 20%： $\le 10$

Subtask6 20%： $K = 2$

Subtask7 20%： $M = 0$

Subtask8 20%：没有特殊的约定.

题解

神题。（orz场正解的神犇szm）
$k\le2$ 的特判即可，下面考虑 $k = 3$ 的情况。
为了方便(解决顺时针同构和环的问题)，把题目转化为第一个点为1，最后一个点为2或3或4的方案数，就变成序列上的计数问题。
先考虑 $m = 0$ 的情况。
先考虑算第一个点为1，最后一个点为2的方案数。直接DP不太可行，先手玩一下前几个数怎么填，发现在填完前几个数后，会转化为类似的子问题：第一个数为 $i + 1$ ,最后一个数为 $i$ ，在其间填上 $i + 2 . . . n$ 的方案数，这正好是原问题翻转的结果。
于是记 $f [i]$ 为第一个数为 $i$ ,最后一个数为 $i + 1$ ，在其间填上 $i + 2 \dots n$ 的方案数， $g [i]$ 为第一个数为i+1,最后一个数为i，在其间填上 $i + 2 \dots n$ 的方案数。发现 $f [i]$ 恰好能由 $g [i + 1], g [i + 2], g [i + 4], g [i + 5]$ 转移过来， $g [i]$ 同理，对于 $i > = n - 6$ 的DP值爆搜即可，于是该问题解决。
对于不满关系的限制，在爆搜和转移时分别判断一下是否合法即可。
再考虑最后一个点为2、3的情况，用刚才的思路，同样可以转移到一些DP值，再判一下初始的位置是否合法即可。