题意:
题目描述:
计算一个满足下列条件的,n x n的矩阵的数量(答案对mod取余)
输入描述:
多组输入,每行输入两个整数,n和mod
- 1 ≤ n ≤ 105
- 1 ≤ mod ≤ 109
- The sum of n does not exceed 107.
输出描述:
输出一个整数表示结果
简单回顾邻接矩阵
思路:
了解了数据结构的邻接矩阵后再看这个矩阵满足的条件,矩阵对称和=0 可以让我们联想到无向图的邻接矩阵,=0表示没有自环。而如果边权表示边数的话,每一行的和为2,说明每个点的度为2。显然是由若干个简单环组成的(简单环就是没有公共点公共边的环),环中元素个数至少是2(没有自环)。
既然我们已经发现了规律,接下来可以来递推了:
1.我们考虑用f[i]表示由n个点组成若干个简单环的方法数。
2. 。
当n>3,由 推 :
3.加入第n个点并且取n-1个点中的任何一个点形成2元环,n-1个方案,此时还有n-2个元素,方式总数为 。
4.加入第n个点并和前取n-1个点中的任意k-1个点形成k 元环, 种方案。此时还有n-k个元素, 种方案。将取出的k个点全排列, 种情况,因为1234和2341和3412是一样的,所以可以确定某一位,然后还剩下k-1个点不确定,所以应该是 种情况。因为是无向图,还要排除首尾一致的情况(即除于2),所以方案数为: 。
5.由3、4可以得到总的方案数为:
。
6.化简雨巨已经讲的很清楚了:
7.写代码的时候注意不要把 后面的 给提出来,不然会wa,因为后面要除2,提出会丢失精度。
Code:
#include <iostream> #define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; typedef long long ll; const int maxn=1e5+7; ll f[maxn],n,mod; int main() { js; 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; }