题目链接：戳这里
参考博客：戳这里 （看的我叹为观止
题意：求有多少个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<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 ()
{
while(~scanf("%lld %lld", &n, &m))
{
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("%lldn", dp[n]);
}
return 0;
}
|
近期评论