牛客多校第一場 B Symmetric Matrix(組合數公式 dp)

NO IMAGE

連結:https://www.nowcoder.com/acm/contest/139/B
來源:牛客網
 

題目描述

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

輸入描述:

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 ≤ 105
* 1 ≤ m ≤ 109
* The sum of n does not exceed 107.

 

題目大意:給出n和m,要你構造出滿足如下條件的n*n的矩陣,

1、矩陣內的元素A[i][j] = {0,1,2}

2、矩陣內的元素A[i][j] = A[j][i]

3、矩陣內的元素A[i][1] A[i][2] A[i][3] … A[i][n]=2 對於所有的 i 都成立

4、矩陣內的元素A[i][i]=0  對於所有的 i 都成立

問你有多少中構造方案

題目思路:可以把這個矩陣看做是無向圖的鄰接矩陣,那麼我們就可以把問題轉化為求無向圖中所有點的度數都為2的圖有多少個。我們考慮f[n]表示n個結點的圖滿足條件的數量。

接下來我們考慮圖中的最後一個點所在的環中有多少個結點,當最後一個環只有兩個結點的時候

C_{n-1}^{1}*f(n-2)=(n-1)*f(n-2)

表示從除最後一個點以外的n-1個點中選出1個點與最後一個點形成環,前n-2個點形成滿足條件的圖的總情況有多少,

再考慮最後一個點所在的環有n-k(k>=2)個結點的情況

我們可以先從前n-1個結點中選出k個結點形成滿足條件的圖,那麼剩下的n-k-1個結點就有(n-k-1)!種形成鏈的方式(因為每個點的度為2,且這n-k-1個結點要與最後一個點形成環,所以這n-k-1個結點只會形成鏈),然後我們再加入最後一個結點與這條鏈的首尾相連形成環,由於首尾的順序與形成的環的方式是無關的,所以這裡要除以一個2將重複的情況去除(比如1,2,3三個結點的全排列中就有1,2,3和3,2,1兩種,由於它是無向圖,所以在加入最後一個結點4之後形成的環都是1-2-3-4-1,就有一種情況重複計算了)。

最後推出來的式子為

C_{n-1}^{k}*f(k)*\frac{(n-k-1)!}{2}

綜上所述可得如下式子

f(n)=(n-1)*f(n-2) \sum_{k=2}^{n-3}C_{n-1}^{k}*f(k)*\frac{(n-k-1)!}{2}

f(n)=(n-1)*f(n-2) \sum_{k=2}^{n-3}\frac{(n-1)!}{k!*(n-k-1)!}*f(k)*\frac{(n-k-1)!}{2}

f(n)=(n-1)*f(n-2) \sum_{k=2}^{n-3}\frac{(n-1)!}{k!}*\frac{f(k)}{2}

通過上述式可得

f(n)-(n-1)*f(n-1)=(n-1)*f(n-2)-(n-1)*(n-2)*f(n-3)/2

f(n)=(n-1)*(f(n-1) f(n-2))-(n-1)*(n-2)*f(n-3)/2

遞推式就推完畢了,具體實現看程式碼:

#include <bits/stdc  .h>
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m 1,r,rt<<1|1
#define pb push_back
#define MP make_pair
#define FIN freopen("in.txt","r",stdin)
#define fuck(x) cout<<"["<<x<<"]"<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
const int MX=1e5 7;
int n,m;
ll f[MX];
int main(){
while(~scanf("%d%d",&n,&m)){
if(m==1){
printf("0\n");
continue;
}
f[1]=0;
f[2]=f[3]=1;
for(int i=4;i<=n;i  ){
f[i]=((i-1)*(f[i-1] f[i-2])%m-(ll)(i-1)*(i-2)/2*f[i-3] m)%m;
}
printf("%lld\n",(f[n] m)%m);
}
return 0;
}