题解：AT_yahoo_procon2019_final_e Espionage

· · 题解

可以把移动的方式转化为一张无向图，同一层之间是一个完全图，相邻的层之间对应点连边，我们要求以下东西的方案数：一个有向环，经过所有点，每个点的入度和出度都刚好为 1。

由于只能在相邻的行之间移动，考虑每次加入一行，我们以下图为例：

把它从中间切开，会得到：

此时应该处理第四行，前三行已经填满，第四行的一些点与下面的点相连，方向确定，剩下的点还没有连边，我们称它们为孤立点。

容易发现，这些确定方向的点一定两两配对，在同一条链上。

我们要做的就是在当前行上加一些横向边，将不同的连通块合并，并且将一些纵向边延续下去。

由于最终只有一个环，并且所有点都在环上，所以我们不能把同一条链提前合成环，也不能在合并完当前行后还留下了孤立点。

如果合并两条链，会得到一条新的链，向下和向上的边都减少 1。如果合并链和孤立点，相当于改变边所在的列，数量不变。如果合并两个孤立点，会得到一条新的链，向上和向下的边都增加 1。

如果先不考虑孤立点，将它们也看做链，合并是简单的。设 s(x,y) 表示将 x 条链合成 y 条链的方案数，链没有标号，显然有：

s(x,y)=\frac{x!}{y!}\binom{x-1}{y-1}

先将 x 条链排序，方案数 x!，然后将它们划分成 y 段，每段内部按顺序合成一条新的链，方案数 \binom{x-1}{y-1}，由于链没有标号，最后还要除以 y!。

但现在我们要求孤立点不能被留下来，考虑容斥，设 M_{x,y} 表示从 x 条链转移到 y 条链方案数，那么：

M_{x,y}=\sum_{i=0}^{\min(n-2x,y)}(-1)^i\cdot\binom{n-2x}{i}\cdot s(n-x-i,y-i)

枚举 i 表示钦定有 i 个孤立点单独留下，因为每条链恰好有两个端点，所以孤立点的总数是 n-2x，从中选出 i 个的方案数就是 \binom{n-2x}{i}。把这些孤立点单独拿出来，还剩下 n-x-i 条链（包含孤立点），将它们合并成剩下的 y-i 条链，方案数就是 s(n-x-i,y-i)。

接下来以此加入一层求答案，设 f_{i,j} 表示目前处理到第 i 层，前 i-1 层留下了 j 条链的方案数，初始状态为 f_{1,0}=1，转移如下：

f_{x,i}=\sum_{j=0}^{n}M_{j,i}\cdot f_{x-1,j}

但最后一行的转移有所不同，因为最终是要合并成一个环的，所以最终不能再留下任何链，直接把所有链和孤立点接成环即可：

ans=\sum_{i=0}^{n}f_{m,i}\cdot(n-i-1)!

但是 m 是很大的，直接转移肯定不行，我们发现每次转移本质上是相同的，因此可以矩阵快速幂：

\begin{bmatrix} f_{x-1,0} & f_{x-1,1} & \cdots & f_{x-1,n-1} & f_{x-1,n} \end{bmatrix} \begin{bmatrix} M_{0,0} & M_{0,1} & \cdots & M_{0,n-1} & M_{0,n}\\ M_{1,0} & M_{1,1} & \cdots & M_{1,n-1} & M_{1,n}\\ & & \cdots\\ \end{bmatrix} = \begin{bmatrix} f_{x,0} & f_{x,1} & \cdots & f_{x,n-1} & f_{x,n} \end{bmatrix}

这样的时间复杂度是 O(n^3\log m)，可以通过。

:::info[参考代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7,N=205;
int n,m,d,f[N],g[N];
struct matrix{
    int a[N][N];
    matrix operator *(matrix x)const{
        matrix y;
        for(int i=0;i<=d;i++){
            for(int j=0;j<=d;j++){
                y.a[i][j]=0;
                for(int k=0;k<=d;k++){
                    y.a[i][j]=(y.a[i][j]+a[i][k]*x.a[k][j])%mod;
                }
            }
        }
        return y;
    }
}; 
matrix getnew(){
    matrix x;
    for(int i=0;i<=d;i++){
        for(int j=0;j<=d;j++){
            x.a[i][j]=0;
        }
        x.a[i][i]=1;
    }
    return x;
}
int qpow1(int x,int y){
    int sum=1;
    while(y){
        if(y&1){
            sum=sum*x%mod;
        }
        x=x*x%mod;
        y/=2;
    }
    return sum;
}
matrix qpow2(matrix x,int y){
    matrix sum=getnew();
    while(y){
        if(y&1){
            sum=sum*x;
        }
        x=x*x;
        y/=2;
    }
    return sum;
}
int C(int x,int y){
    return f[x]*g[x-y]%mod*g[y]%mod;
}
int S(int x,int y){
    if(!x&&!y){
        return 1;
    }
    if(!x||!y){
        return 0;
    }
    return f[x]*g[y]%mod*C(x-1,y-1)%mod;
}
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    d=n/2;
    f[0]=1;
    for(int i=1;i<=n;i++){
        f[i]=f[i-1]*i%mod;
    }
    g[n]=qpow1(f[n],mod-2);
    for(int i=n;i;i--){
        g[i-1]=g[i]*i%mod;
    }
    matrix M;
    for(int i=0;i<=d;i++){
        for(int j=0;j<=d;j++){
            M.a[i][j]=0;
            for(int k=0;k<=min(n-2*i,j);k++){
                M.a[i][j]=(M.a[i][j]+(k%2?-1:1)*C(n-2*i,k)*S(n-i-k,j-k))%mod;
            }
        }
    }
    matrix s;
    for(int i=0;i<=d;i++){
        for(int j=0;j<=d;j++){
            s.a[i][j]=0;
        }
    }
    s.a[0][0]=1;
    matrix t=s*qpow2(M,m-1);
    int ans=0;
    for(int i=0;i<=d;i++){
        ans=(ans+t.a[0][i]*f[n-i-1])%mod;
    }
    cout<<(ans+mod)%mod;
    return 0;
}

:::