【每日一题】Symmetric Matrix

建议改成：自闭矩阵

题目

题目描述：

计算一个满足下列条件的，n x n的矩阵的数量（答案对mod取余）

* A_{i, j} ∈ {0, 1, 2} for all 1 ≤ i, j ≤ n.
* A_{i, j} = A_{j, i} for all 1 ≤ i, j ≤ n.
* A_{i, 1} + A_{i, 2} + ... + A_{i, n} = 2 for all 1 ≤ i ≤ n.
* A_{1, 1} = A_{2, 2} = ... = A_{n, n} = 0.

输入描述：

多组输入，每行输入两个整数，n和mod

* 1 ≤ n ≤ 10⁵
* 1 ≤ mod ≤ 10⁹
* The sum of n does not exceed 10⁷.

输出描述：

输出一个整数表示结果

解析

讨厌英文题，超级讨厌英文题。

这道题看不出什么东西，但是我们看到n的上限也就是数组上限，这也许就是一道递推题呢？

所以我们（看大佬）找规律：

首先，我们这个矩阵假设用一个二维数组表示，按照题目要求：这是一个对称矩阵，行和为2（因为对称，所以列和也为2），主对角线为0。
我们看到这样的矩阵会想到什么？对了！什么都想不到！（我们应该想到这可以看做一个一张图的邻接矩阵）。
根据这个矩阵的特点：每个节点的度最大为2（为什么说是最大呢？因为题目说边权可以为2，而行和一定为2。所以可以只连一个节点）。
既然如此，我们这张图一定是由1或多个简单环组成的。

既然我们已经发现了规律，所以我们可以来递推了：

加入我们要知道f[n + 1]的值，我们有两种选择：<1>单独和某点成一条权为2的边；<2>和多个点成环。
首先单独取出一个点：我们从n个点中取一个点有n种取法，所以我们的可以得到公式： $f[n + 1] = n \times f[n - 1] + ……$ 。
然后取出多个点：假如从n个点中取k个点，我们有 $C_{n}^{k}$ 种取法。再将这k个点排列，又有 $A_{k}^{k}$ 种方法（也就是k!种）。不过由于第n + 1个节点，连接首尾，又是无向图，所以要除2。于是公式就是： $f[n + 1] = …… + \frac{1}{2} \sum_{k = 3}^{n}{C_{n}^{k} \times k! \times f[n - k]}$ 。
所以最后就得到公式： $f[n + 1] = n \times f[n - 1] + \frac{1}{2} \sum_{k = 3}^{n}{C_{n}^{k} \times k! \times f[n - k]}$ 。
最后就是化简，可以得到公式： $f[n] = (n - 1)(f[n - 1] + f[n - 2]) + \frac{1}{2}(n - 1)( n - 2)f[n - 3]$ 。

最后写代码就没有很大的问题了：

输入该输入的变量。
用一个数组递推得到答案。

AC代码

#include <iostream>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e5 + 7;
ll f[MAX];
//全局变量区

int main() {
    js;
    int n, mod;
    f[1] = 0; f[2] = f[3] = 1;
    while (cin >> n >> mod) {
        for (ll i = 4; i <= n; i++)
            f[i] = ((i - 1) * (f[i - 1] + f[i - 2]) - (i - 1) * (i - 2) / 2 * f[i - 3]) % mod;
        cout << (f[n] + mod) % mod << endl;
    }
    return 0;
}
//函数区