题解：P11817 [PA 2019 Final] 数图 / Grafy

· · 题解

考虑邻接矩阵，相当于一个 n\times n 的 01 矩阵，每行每列和为 2，对角线上全为 0，求方案数。

先容斥，钦定对角线的一个子集 T 填 1。发现去掉这些 1 后这些位置不能填数，不好处理。

好做的形式是对角线的子集 \geq 1，其他位置是 0 或 1，这样把钦定的子集减一后对角线和其他格子就没有区别了。

具体地，把钦定的子集减一后，剩下的限制：n\times n 的 01 矩阵，每格填 0 或 1，有 |T| 行 |T| 列和为 1，其余行列和为 2。

记 f_{i,j,k,l} 表示有一个 (i+j)\times(k+l) 的 01 矩阵，要求前 i 行、前 k 列和为 1，后 j 行、后 l 列和为 2。

状态数是 O(n^3)（因为 i+2j=k+2l，l 可以用 i，j，k 表示），转移枚举第一行的 1 填在哪，做到 O(1)，所以 f 数组可以 O(n^3) 求出。

容斥的时候钦定对角线的子集 \geq 1，其他位置是 0，1 或 2，这个方案数可以用 f 求出（枚举其他位置哪些填 2）。

因此总时空复杂度 O(n^3)，做到空间最劣解！！！11。。

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define debug(x) (cerr<<#x": "<<(x)<<endl)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;

bool ST;
const int N=510;
int f[N][N][N];
int n;ll P;
ll CC[N][N];ll C(ll x,ll y){return (x>=y&&y>=0)?CC[x][y]:0;}
bool ED;
int32_t main(){
    debug(fabs(&ST-&ED)/(1<<20));
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>n>>P;
    rep(i,0,n) CC[i][0]=1;
    rep(i,1,n) rep(j,1,i) CC[i][j]=(CC[i-1][j-1]+CC[i-1][j])%P;
    int k;
    f[0][0][0]=1;
    rep(i,0,n) for(int j=0;i+j<=n;j++) rep(l,0,n){
        k=i+2*j-2*l;if(k<0) continue;
        if(i==0){
            if(j==0&&k==0) continue;
            if(k>=2) f[i][j][l]=(f[i][j][l]+(ll)f[i][j-1][l]*(k*(k-1)/2))%P;
            if(k>=1&&l>=1) f[i][j][l]=(f[i][j][l]+(ll)f[i][j-1][l-1]*k*l)%P;
            if(l>=2) f[i][j][l]=(f[i][j][l]+(ll)f[i][j-1][l-2]*(l*(l-1)/2))%P;
        }
        else{
            f[i][j][l]=(f[i][j][l]+(ll)f[i-1][j][l]*k)%P;
            f[i][j][l]=(f[i][j][l]+(ll)f[i-1][j][l-1]*l)%P;
        }
    }
    ll ans=0;
    rep(i,0,n){
        ll ret=0;
        rep(j,0,n-i) (ret+=C(n-i,j)*f[i][n-i-j][n-i-j])%=P;
        ret=ret*C(n,i)%P;
        if(i&1) (ans+=P-ret)%=P;
        else (ans+=ret)%=P;
    }
    cout<<ans<<'\n';
    return 0;
}