NC17134 Symmetric Matrix（dp+数学）

链接：https://ac.nowcoder.com/acm/problem/17134

solution

首先看一下 $n \times n$n×n 的方阵需要满足的条件：

1. 矩阵中的任意元素 $a_{i,j} \in \{0,1,2\}$ai,j​∈{0,1,2}
2. 满足对称矩阵
3. 每行的和是2
4. 主对角线都是0

这些条件加起来就是无向图的邻接矩阵表示，$a_{i,j}$ai,j​ 就是点 $i$i 到点 $j$j 的权值，我们把这个权值定义为边的个数，即点 $i$i 到点 $j$j 的边的个数，这就是数形结合的思想。
转化成图以后我们发现，主对角线都是0，说明这个图没有自环；每行的和都是2，也就是每个点的度都是2，这就意味着这个图是由若干个环组成的，且没有自环，环之间没有公共部分。
我们考虑递推 $dp_{x}$dpx​ 表示 $x$x 个点可以组成若干环的不同方案数，那么显然 $dp_1=0,dp_2=1,dp_3=1$dp1​=0,dp2​=1,dp3​=1，然后我们再考虑转移，已经有 $n-1$n−1 个点时再加入第 $n$n 个点：

• 加入的第 $n$n 个点与 $n-1$n−1 个点中的一个构成一个二元环，这个点可以有 $n-1$n−1 种选择，然后剩下的 $n-2$n−2 个点有 $dp_{n-2}$dpn−2​ 种不同的方案，所以方案数为 $(n-1)\times dp_{n-2}$(n−1)×dpn−2​ 。
• 加入的第 $n$n 个点与之前的 $k-1$k−1 个点构成一个 $k$k 元环（$k\geq 3$k≥3，因为二元环上面已经讨论过了），选择前面的 $k-1$k−1 个点共有 $C_{n-1}^{k-1}$Cn−1k−1​ 中方法，这个 $k$k 元环的圆排列一共有 $\frac{(k-1)!}{2}$2(k−1)!​，剩下的 $n-k$n−k 个点有 $dp_{n-k}$dpn−k​ 种方案，所以方案数是 $\sum_{k=3}^{n} (C_{n-1}^{k-1}\times\frac{(k-1)!}{2}\times dp_{n-k})$∑k=3n​(Cn−1k−1​×2(k−1)!​×dpn−k​) 。

所以最后的状态转移方程就可以写成 $dp_{n}=(n-1)\times dp_{n-2}+\sum_{k=3}^{n} (C_{n-1}^{k-1}\times\frac{(k-1)!}{2}\times dp_{n-k})$dpn​=(n−1)×dpn−2​+k=3∑n​(Cn−1k−1​×2(k−1)!​×dpn−k​) 然后我们需要处理这个方程：
$dp_{n}=(n-1)\times dp_{n-2}+\sum_{k=3}^{n} (\frac{(n-1)!}{(k-1) !\times (n-k)!} \times\frac{(k-1)!}{2}\times dp_{n-k})$dpn​=(n−1)×dpn−2​+k=3∑n​((k−1)!×(n−k)!(n−1)!​×2(k−1)!​×dpn−k​) $=(n-1)\times dp_{n-2}+\sum_{k=3}^{n} (\frac{(n-1)!}{(n-k)!\times 2} \times dp_{n-k})$=(n−1)×dpn−2​+k=3∑n​((n−k)!×2(n−1)!​×dpn−k​) 这里 $k$k 表示第 $n$n 个点所在的 $k$k 元环，我们设 $x=n-k$x=n−k，$(3\le k\le n)$(3≤k≤n) ，那么 $x$x 就表示其他的点 $=(n-1)\times dp_{n-2}+\sum_{x=0}^{n-3} (\frac{(n-1)!}{x!\times 2} \times dp_{x})$=(n−1)×dpn−2​+x=0∑n−3​(x!×2(n−1)!​×dpx​) $dp_{n-1}=(n-2)\times dp_{n-3}+\sum_{x=0}^{n-4} (\frac{(n-2)!}{x!\times 2} \times dp_{x})$dpn−1​=(n−2)×dpn−3​+x=0∑n−4​(x!×2(n−2)!​×dpx​)
观察比较 $dp_{n}$dpn​ 和 $dp_{n-1}$dpn−1​ 可以发现，两式的 $\sum$∑ 部分只相差一项，所以令
$dp_{n}-(n-1)\times dp_{n-1}=(n-1)\times dp_{n-2}-(n-1)\times(n-2)\times dp_{n-3}+\frac{(n-1)!}{(n-3)!\times 2} \times dp_{n-3}$dpn​−(n−1)×dpn−1​=(n−1)×dpn−2​−(n−1)×(n−2)×dpn−3​+(n−3)!×2(n−1)!​×dpn−3​ 最后，移项得：
$dp_{n}=(n-1)\times (dp_{n-1}+dp_{n-2})-\frac{1}{2}(n-1)\times(n-2)\times dp_{n-3}$dpn​=(n−1)×(dpn−1​+dpn−2​)−21​(n−1)×(n−2)×dpn−3​

注意减法取模和 long long
参考题解 【每日一题】4月29日题目精讲 dp+数学、Symmetric Matrix

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int dp[N];
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    ll n, m;
    dp[1] = 0, dp[2] = 1, dp[3] = 1;
    while (cin >> n >> m)
    {
        for (int i = 4; i <= n; i++)
            dp[i] = ((1LL * (i - 1) * (dp[i - 1] + dp[i - 2]) % m - 1LL * (i - 1) * (i - 2) / 2 * dp[i - 3] % m) % m + m) % m;
        cout << dp[n] << endl;
    }
    return 0;
}