题解：AT_yahoo_procon2019_final_e Espionage

· · 题解

题目分析

题意相当于求该图的哈密顿回路个数，这是一个 m 层，每层是一个 n 个点的完全图 K_n，相邻层之间对应点相连的图。

考虑 DP，尝试划分子问题，直接观察上面建出来的图就可以发现去切完全图显然不如切层，也就是说按层来划分比按栋来划分更有前途。

那么就扫层，假设当前扫到了第 i 层，我们已经将 i 层之前的所有信息都处理好了，由于我们相当于在 i 与 i+1 层之间切了一刀，那么会将整个哈密顿回路切出来许多的链，这些链全在前 i 层，并且端点一定都在第 i 层上。

为了后续更方便的实现，我们先给这个哈密顿回路定向，那么现在就是切出来许多有向路径，每条路径的入端和出端一定都在第 i 层上，且这些有向路径一定覆盖了前 i-1 层中的每个点。

因此可以设 f_{i,j} 表示只考虑前 i 层，哈密顿回路被拆开成了 j 条有向链的方案数。

考虑转移到 i+1 层去，我们需要在 i 层内部连边，还需要从 i 层往 i+1 层或 i+1 往 i 层连边。先考虑前者，我们只需要保证每个点的出入度都为 1 即可，所以当我们确定好 i 层内部的连边时，i 与 i+1 层之间的方案数就固定下来了，具体的，对于连好后第 i 层中的点，没有入边的就从 i+1 层连下来，没有出边的就从 i 层连上去，限制就是连完 i 层内部的边后不能存在孤立点（入边出边都没有的），和不能连成环。

现在再来考虑 i 层内部连边的方案数，如果没有不能存在孤立点的限制是非常简单的，将孤立点看作链，然后枚举将这所有的有向链划分成几组，每组内依次连边，但是现在不能存在孤立点，所以考虑容斥，设 F(i) 表示恰好有 i 个孤立点的方案，G(i) 表示钦定有 i 个孤立点的方案，二项式反演一下即可。

那么现在就能从 i 层转移到 i+1 层了，复杂度可以做到 \mathcal{O}(n^3) \sim \mathcal{O}(n^4)，但是这个只是一层的转移，再套个 m 复杂度爆炸，考虑到每层之间转移其实本质一样，于是我们就可以将一层的转移写成一个 n^2 的矩阵，m_{j,k} 表示从 f_{i,j} 转移到 f_{i+1,k} 的系数，转移就成了 f 向量乘上转移矩阵了，然后一共 m 层要乘 m 次就直接矩阵快速幂，总复杂度 \mathcal{O}(n^3 \log n)。

Code

#include<bits/stdc++.h>
using namespace std;
//
const int maxn=200+10;
const int mod=1e9+7;
inline int add(const int x,const int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(const int x,const int y){return x-y<0?x-y+mod:x-y;}
inline int Pow(int x,int y){
    int s=1;
    for(;y;x=1ll*x*x%mod,y>>=1)if(y&1)s=1ll*s*x%mod;
    return s;
}
int n,m,ans;
int fac[maxn],ifac[maxn];
inline int C(int n,int m){return n<0||m<0||n<m?0:1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
void init(int n){
    fac[0]=ifac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=Pow(fac[n],mod-2);
    for(int i=n-1;i>=1;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
inline int calc(int n,int k){return !n&&!k?1:1ll*fac[n]*C(n-1,k-1)%mod*ifac[k]%mod;}
struct Matrix{
    int mat[maxn][maxn];
    Matrix(){memset(mat,0,sizeof(mat));}
}f,a;
inline Matrix operator * (const Matrix &a,const Matrix &b){
    Matrix c;
    for(int k=0;k<=n;k++)for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)c.mat[i][j]=add(c.mat[i][j],1ll*a.mat[i][k]*b.mat[k][j]%mod);
    return c;
}
inline Matrix Pow(Matrix x,int y){
    Matrix s;
    for(int i=0;i<=n;i++)s.mat[i][i]=1;
    for(;y;x=x*x,y>>=1)if(y&1)s=s*x;
    return s;
}
int main(){

    cin>>n>>m;
    init(n);
    for(int i=0;2*i<=n;i++){ //上一行i条链，这一行n-2i个孤立点
        for(int j=1;j<=n-i;j++){ //合并为j条链
            int sum=0;
            for(int k=0;k<=n-2*i&&k<=j;k++){ //二项式反演
                if(k&1)sum=sub(sum,1ll*C(n-2*i,k)*calc(n-i-k,j-k)%mod);
                else sum=add(sum,1ll*C(n-2*i,k)*calc(n-i-k,j-k)%mod);
            }
            a.mat[i][j]=sum;
        }
    }
    f.mat[0][0]=1;
    f=f*Pow(a,m-1);
    ans=0;
    for(int i=1;i<=n;i++)ans=add(ans,1ll*f.mat[0][i]*fac[n-i-1]%mod);
    cout<<ans<<'\n';

    return 0;
}