1. 题目

传送门=￣ω￣=

题意：求有多少个长度为 $n$的排列，使得它相邻的两项互质，对 $m$取模。

$n \leq 28, m \leq 3 \times 10 ^ 4$

2. 题解

QAQ 居然找到了 zyf 蒯的题 QwQ

首先有个 Naive 的想法：

$f[i][j]$表示当前还没被选择集合为 $i$，最后一个选的元素为 $j$的方案数。

这玩意复杂度是 $O(2 ^ n \times n ^ 2)$

非常不妙

然后我们就需要一些小技巧：

对于 “互质” 这个事情，含有相同质因数才不互质

因此我们可以把质因数相同的数字分到一组，因为质因数个数与互质并没有关系，我们只关心是否含有某个质因数。

比如 $6$和 $12$会分到一组，$4$和 $8$会分到一组，但是 $2$和 $6$不会分到一组。

这样我们会发现——28 个数字只会分出 18 组。

然后优化一下——$1, 17, 19, 23$这 4 个数字与别的数字都互质，因此它们可以分到一组，这样最后只会分出 15 组了。

现在等于只要生成一个长度为 15 的排列，但是每个数字可以选的次数不同。

那么就不能简单地用二进制表示状态了，得用 “变进制”

怎么个 “变进制” 法呢？

在二进制里，我们是逢二进一

现在我们对于第 $i$类的数字个数为 $c[i]$，那么状态的第 $i$位就逢 $c[i] + 1$进一。

$c[i]$还要 $+ 1$的原因是可以不选，即我们要用这一位表示出 $[0, c[i]]$，一共 $c[i] + 1$个状态。

每一位的进制不同，就叫变进制状压。

这样表示一个状态的数字是唯一的，不会有冲突。

如果还不懂的话可以参考下面的代码，其中 hs()函数是把一个状态压成一个整数，uhs()函数是取状态的某一位的值。

有了这个状压玩法就和最开始的二进制状压一样了

$f[i][j]$表示当前每一类的剩余数字数量状态为 $i$，最后选择的是第 $j$类的方案数。

注意因为每一类里的数字还有先选和后选之分，因此答案需要乘上 $\Pi (C[i]!)$

丢代码跑 QvQ：

#include <bits/stdc++.h>

#define REG register

using namespace std;

const int prm[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 0};

template <typename _Tp> inline void IN(_Tp& dig)
{
    REG char c; REG bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int T, n, m, blk[30], x[16], tp, c[15];

bool book[15][15];

void Init()
{
    REG int h[1 << 6] = {0}, d[15] = {0}, cnt = 0;
    for (REG int i = 1; i <= 28; i += 1)
    {
        if (i == 1 || i == 17 || i == 19 || i == 23) {blk[i] = 0; continue;}
        REG int st = 0;
        for (REG int j = 0; j <= 5; j += 1)
            if (i % prm[j] == 0)
                st |= (1 << j);
        if (h[st]) blk[i] = h[st];
        else blk[i] = h[st] = ++cnt, d[cnt] = st;
    }
    for (REG int i = 0; i <= cnt; i += 1)
        for (REG int j = 0; j <= cnt; j += 1)
            if (d[i] & d[j]) book[i][j] = 0;
            else book[i][j] = 1;
}

inline int hs(int (&a)[15])
{
    REG int res = 0;
    for (REG int i = 0; i <= tp; i += 1) res += a[i] * x[i];
    return res;
}

inline int uhs(REG int st, REG int a)
{
    return (st % x[a + 1]) / x[a];
}

int f[2000000][15], ans;

inline int pls(REG int a, REG int b) {return a + b >= m ? a + b - m : a + b;}

int Dfs(REG int rem, REG int p)
{
    if (!rem) return 1;
    if (f[rem][p] != -1) return f[rem][p];
    int& F = f[rem][p]; F = 0;
    for (REG int i = 0; i <= tp; i += 1)
        if (book[p][i] && uhs(rem, i))
            F = pls(F, Dfs(rem - x[i], i));
    return F;
}

int main(int argc, char const* argv[])
{
    Init(), IN(T);
    while (T--)
    {
        IN(n), IN(m), tp = 0, memset(f, -1, sizeof(f)), memset(x, 0, sizeof(x));
        if (m == 1) {puts("0"); continue;}
        for (REG int i = 1; i <= n; i += 1)
            tp = max(tp, blk[i]), x[blk[i]]++;
        for (REG int i = 0; i <= tp; i += 1) c[i] = x[i], x[i]++;
        for (REG int i = tp + 1; i >= 1; i -= 1) x[i] = x[i - 1];
        x[0] = 1;
        for (REG int i = 1; i <= tp + 1; i += 1) x[i] *= x[i - 1];
        ans = Dfs(hs(c), 0);
        for (REG int i = 0; i <= tp; i += 1)
            while (c[i]) ans = ans * c[i] % m, c[i]--;
        printf("%d\n", ans);
    }
    return 0;
}