牛客网多校训练第一场 B - Symmetric Matrix（dp）

链接：

https://www.nowcoder.com/acm/contest/139/B

 

题意：

求满足以下条件的n*n矩阵A的数量模m：

A(i,j) ∈ {0,1,2}, 1≤i,j≤n.

A(i,j) = A(j,i), 1≤i,j≤n.

A(i,1) + A(i,2) + ... + A(i,n) = 2, 1≤i≤n.

A(1,1) = A(2,2) = ... = A(n,n) = 0.

其中1≤n≤1e5, 1≤m≤1e9。

 

分析：

把矩阵看成无向图的邻接矩阵，即要求所有点度为2，即每个点都属于一个环。

设d(n)表示n个点满足条件的图的数量。

思考每加入一个新点，如何从已知状态转移。

1.从前面的n-1个点中选出1个点与新点构成环，有(n-1)d(n-2)种方案。

2.从前面的n-1个点中选出k个点，剩下的点与新点连成环，

有sum(C(n-1,k)*(n-1-k)!/2)(2≤k≤n-3)种方案，

因为剩下的点与新点连成环时的对称性，所以要除以2。

将以上两式化简相加，得d(n) = (n-1)d(n-2) + sum((n-1)!d(k)/k!/2)(2≤k≤n-3)。

设f(n) = sum((n-1)!d(k)/k!/2)(2≤k≤n-3)。

可以发现，f(n)也是可以递推的，即f(n) = (n-1)f(n-1) + (n-1)(n-2)d(n-3)/2。

所以，线性时间递推f和d数组即可。

 

代码：

import java.io.*;
import java.util.*;
 
public class Main {
    Scanner cin = new Scanner(new BufferedInputStream(System.in));
    final int UP = (int)1e5 + 5;
    long d[] = new long[UP], f[] = new long[UP];
     
    void MAIN() {
        while(cin.hasNext()) {
            int n = cin.nextInt();
            long m = cin.nextInt();
             
            d[2] = d[3] = f[3] = 1 % m;
            for(int i = 4; i <= n; i++) {
                f[i] = ((i-1) * f[i-1] % m + (long)(i-1) * (i-2) / 2 % m * d[i-3] % m) % m;
                d[i] = ((i-1) * d[i-2] % m + f[i]) % m;
            }
            System.out.println(d[n]);
        }
    }
     
    public static void main(String args[]) { new Main().MAIN(); }
}