2018牛客网暑期多校 B-Symmetric Matrix 【构造+dp】

发表于 | 分类于

题目链接：戳这里
参考博客：戳这里 （看的我叹为观止

题意：求有多少个n*n矩阵满足下列条件

  • 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.

解题思路：根据上面的条件我们会发现这个矩阵其实可以类比图的邻接矩阵。每个点的度为2相当于该点在一个环内。


解释以下在t环内的情况：

其实就是从n-1个点中找t-1个点，看能构成多少个环，对t个点进行全排列，去掉同一个环里同构的情况就是t环内的方案数。同构的情况有：
1.在同一个环内，顺时针与逆时针的排列不同，比如1234和1432
2.在顺时针中，起点不同的排列不同，比如1234与2341

因此总的方案数需/(2 * t)

附ac代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
ll dp[maxn];
ll n;
ll m;
int main()
{
 
    while(~scanf("%lld %lld", &n, &m))
    {
     //   memset(dp, 0, sizeof(dp));
        dp[1] = 0, dp[2] = 1 % m, dp[3] = 1 % m;
        for(ll i = 4; i <= n; ++i)
        {
            dp[i] = (((i - 1) * dp[i - 1]) % m + ((i - 1) * dp[i - 2]) % m - (( (i - 1) * (i - 2) / 2) % m * dp[i - 3]) % m) % m;
            dp[i] = (dp[i] + m) % m;
        }
        printf("%lld\n", dp[n]);
    }
    return 0;
}