首先注意到每个房间必须去一次没啥意义，因为这个限制和不能出现排列是没有交叉的，所以直接减去房间出现不全的方案数，这个直接容斥解决，即减去 ：

$$\sum\limits_{i=1}^{m-1} (-1)^{i+1}\binom{m}{i}(m-i-1)^{n-1}(m-i) $$

含义就是枚举有几个元素没出现，然后假如 $i$ 个没有出现，那就把它们选出来，剩下的元素中，第一个位置 $m-i$ 种填法，后面的和上一个不一样，所以是 $m-i-1$。

sub1

直接爆搜，或者你直接注意到除了 $n=5,m=4$ 答案是 $24$ 之外答案都是 $0$。

sub2

我们只需要确定后 $m$ 个数的局面就可以往后填数，于是设 $f_{i,S}$ 表示已经填完了 $i$，后 $S$ 个数的填数状态，然后暴力转移。

$n$ 非常大，所以上一个矩阵快速幂就可解决了。

复杂度取决于你 $S$ 的方案有多少。

sub3

考虑一个朴素的 dp，设 $f_{i,j}$ 表示现在填了前 $i$ 个位置，最多后 $j$ 个位置是互不相同的的方案数，转移系数很简单推，只要不允许 $f_{i,m}$ 出现就行。

时间复杂度 $O(nm)$。

sub4

把刚刚的 dp 上一个矩阵快速幂即可。

时间复杂度 $O(m^3\log n)$。

sub5

如果我们去掉相邻位置不相同这个限制，怎么做这个问题呢？

考虑容斥解决这个问题。

假如枚举了一个位置集合 $S$ 表示所有排列的开头位置，那么无交的排列之间没有影响，有交的段拿出来，假如有 $k$ 个元素，位置分别 $p_1,p_2,...,p_k$，方案数显然就是 $m!\prod\limits_{i=2}^n(p_i-p_{i-1})!$。

接下来使用生成函数刻画容斥，上面的式子启发我们考虑连续段的生成函数。

具体来说，设 $F(x)=\sum\limits_{i=0}^{+\infty}a_ix^i$，$a_i$ 表示长度为 $i$ 的序列中，这个序列每一个位置都被排列覆盖的带容斥系数的方案数。

这样的序列可以看作是开头一个完整排列，后面若干个小段排列构成的序列。

由于第一个位置必然是排列开头，所以先在外面乘一个 $-m!x^m$，然后考虑后面的小段，一个小段的生成函数 $G(x)$ 显然是 $-\sum\limits_{i=1}^{m-1}i!x^i$，然后把它们拼在一起就是 $\sum\limits_{i=0}^{+\infty}G^i(x)=\dfrac{1}{1-G(x)}$，所以 $F(x)=\dfrac{-m!x^m}{1-G(x)}$。

于是把这些段和没有仍和限制的位置综合到一起，就是 $mx+F(x)$，这是我们每一次可以在序列里面填的东西，继续类似 $G$ 一样的组装，可以得到答案的生成函数是 $H(x)=\dfrac{1}{1-mx-F(x)}$，其中 $[x^n]H(x)$ 就是答案。

接下来你会发现这个做法直接去做原问题，即要求相邻位置不同是类似的。

比较自然的想法就是第一个位置有 $m$ 种填法，然后后面的位置只能有 $m-1$ 种，对应到生成函数就是把式子改成 $F(x)=\dfrac{-(m-1)!\times (m-1)x^m}{1-G(x)},H(x)=\dfrac{mx}{1-(m-1)x-F(x)}$，然后答案依旧是 $[x^n]H(x)$。

但是这样有点问题，因为我这样似乎不能钦定 $1$ 这个位置开头的 $m$ 个数是排列的情况，即除了序列前 $m$ 个数的子段可以是排列，其他不能为排列的方案数。不过也好解决，不妨计算出长度 $n+1$ 的答案，去掉第一个数的影响，也就是除以 $m-1$ 就好了，答案就是 $\dfrac{[x^{n+1}]H(x)}{m-1}$。

如果你不会求这个式子，那你可以用多项式除法暴力算出来答案，时间复杂度 $O(n\log n)$。

sub 6&7

考虑求最后的答案，式子形如 $[x^n]\dfrac{P(x)}{Q(x)}$，而 $P,Q$ 都是长度为 $m$ 的多项式，使用 Bostan_Mori 算法即可，时间复杂度为 $O(m\log m\log n)$。

似乎 Bostan_Mori 算法不是那么广为人知所以简单介绍一下：

试图计算 $[x^n]\dfrac{P(x)}{Q(x)}$，假设 $n$ 为偶数：

$[x^n]\dfrac{P(x)}{Q(x)}=[x^n]\dfrac{P(x)Q(-x)}{Q(x)Q(-x)}$。

注意到分母为偶函数，即奇数次项系数为 $0$，于是可以也只保留分子的偶次项系数，这样就可以将奇数次项消除，问题成功减半，处理之后的式子变成 $[x^\frac{n}{2}\dfrac{P_2(x)}{Q_2(x)}]$。

如果 $n$ 为奇数，那么分母保留奇次项就可以了，其他的都是一样的。

每次折半的时间复杂度是 $O(m\log m)$，执行 $O(\log n)$ 次，总时间复杂度就是 $O(m\log m\log n)$。

sub6 留给常数不太好的实现方式。