【每日一题】4月29日Symmetric Matrix

Symmetric Matrix

http://www.nowcoder.com/questionTerminal/3d9b8fa55fc5426594d047fa594a068b

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

Count the number of n x n matrices A satisfying the following condition modulo m.
* 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.

输入描述:

The input consists of several test cases and is terminated by end-of-file.
Each test case contains two integers n and m.

输出描述:

For each test case, print an integer which denotes the result.

示例1

输入

复制

3 1000000000
100000 1000000000

输出

复制

1
507109376

备注:

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

解题思路

英文题面，大概意思是n * n的方针，每个位置只能放0，1，2，主对角只能放0，并且矩阵对称，而且矩阵列和为2。
输入矩阵规模n和模数m；问n阶方阵上述方法填的合法矩阵对m取模的数量。
太菜了，不过给我感觉是动态规划的题目，那就存在递推式，先算前5项吧。
n = 1; sum = 0
n = 2; sum = 1
n = 3; sum = 1
n = 4; sum = 6
n = 5; sum = 22
然后肉眼看也行，当然还有一个更好的选择OEIS，输入1 1 6 22，你会发现这样一个图片
图片说明

找到递推式 $图片说明$

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43650032&returnHomeType=1&uid=919749006

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e5 + 7;
ll dp[N] = { 0,0,1,1 };
ll n, m;

int main() {
    while (~scanf("%lld %lld", &n, &m)) {
        for (ll i = 4; i <= n; ++i)

            // 注意 1e5*1e5*1e9 = 1e19 爆了ll， 把除号放在前面 5e18 没爆9e18...
            dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2]) - (i - 1) * (i - 2) / 2 * dp[i - 3]) % m;
        printf("%lld\n", (dp[n] + m) % m);
    }
    return 0;
}

然后……就这样好像不太友好。不是啥时候都要OEIS使的，还是推个式子吧！
把这个矩阵转换成图的邻接矩阵，会很好推的。
矩阵点 $图片说明$ 值代表i和j存在几条边相连。题目给定的条件，不可能自己和自己相连。
大概画个2种情况的图：

那么我们如果求解到了n-1阶方阵的方案数，对于新加的n节点，与前面n - 1个节点连边情况如下：
情况1：选定一个节点与n连双向边有n - 1种选择方法，其余n - 2个节点自由连接。
情况2：选定一个节点和n连单向边，n - 1个节点自由连接，最终一定会存在一个节点没连接2次，这个节点在和n节点连接。
情况2会存在重复，想想为什么，先选定一个节点x，连接n，最后剩一个y，在连接n，与先y后x，是同一种方案。
那么我们只需要减掉重复部分就行了，选x是n - 1，选y是n - 2，那么剩余n - 3是自由组合，一半数据重复，减掉这一半就行了。
那么也可以得到上面耳洞递推式。