【每日一题】Symmetric Matrix
建 议 改 成：自 闭 矩 阵
题目
题目描述：
计算一个满足下列条件的，n x n的矩阵的数量（答案对mod取余）
* Ai, j ∈ {0, 1, 2} for all 1 ≤ i, j ≤ n.
* Ai, j = Aj, i for all 1 ≤ i, j ≤ n.
* Ai, 1 + Ai, 2 + ... + Ai, n = 2 for all 1 ≤ i ≤ n.
* A1, 1 = A2, 2 = ... = An, n = 0.
* Ai, j = Aj, i for all 1 ≤ i, j ≤ n.
* Ai, 1 + Ai, 2 + ... + Ai, n = 2 for all 1 ≤ i ≤ n.
* A1, 1 = A2, 2 = ... = An, n = 0.
输入描述：
多组输入，每行输入两个整数，n和mod
* 1 ≤ n ≤ 105
* 1 ≤ mod ≤ 109
* The sum of n does not exceed 107.
* 1 ≤ mod ≤ 109
* The sum of n does not exceed 107.
输出描述：
输出一个整数表示结果
解析
讨厌英文题，超级讨厌英文题。
这道题看不出什么东西，但是我们看到n的上限也就是数组上限，这也许就是一道递推题呢？
所以我们（看大佬）找规律：
- 首先，我们这个矩阵假设用一个二维数组表示，按照题目要求：这是一个对称矩阵，行和为2（因为对称，所以列和也为2），主对角线为0。
- 我们看到这样的矩阵会想到什么？对了！什么都想不到！（我们应该想到这可以看做一个一张图的邻接矩阵）。
- 根据这个矩阵的特点：每个节点的度最大为2（为什么说是最大呢？因为题目说边权可以为2，而行和一定为2。所以可以只连一个节点）。
- 既然如此，我们这张图一定是由1或多个简单环组成的。
既然我们已经发现了规律，所以我们可以来递推了：
- 加入我们要知道f[n + 1]的值，我们有两种选择：<1>单独和某点成一条权为2的边；<2>和多个点成环。
- 首先单独取出一个点：我们从n个点中取一个点有n种取法，所以我们的可以得到公式：
。
- 然后取出多个点：假如从n个点中取k个点，我们有
种取法。再将这k个点排列，又有
种方法（也就是k!种）。不过由于第n + 1个节点，连接首尾，又是无向图，所以要除2。于是公式就是：
。
- 所以最后就得到公式：
。
- 最后就是化简，可以得到公式：
。
最后写代码就没有很大的问题了：
- 输入该输入的变量。
- 用一个数组递推得到答案。
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;
}
//函数区 每日一题 文章被收录于专栏
憨憨的专栏
