题解：AT_yahoo_procon2019_final_e Espionage

· · 题解

我很菜，所以我只能做到 O(n^4 + n^3 \log m)，虽然 n 能带一个 \frac{1}{2} 的常数总之跑的很快就是了。

先只考虑在竖直方向的移动，观察每一层，我们发现会有一些往上的和往下的接口，我们会有这样的一个思路：先考虑这个点向上和向下走的这些事件，然后把平移操作插空用组合数算，这是大概的一个思路。

然后不妨考虑一个 DP，f_{i,x} 表示第 i 层有 x 个向上的接口的方案数，转移需要枚举下一层的接口数量 y，并用 f_{i,x} \times t_{x,y} \to f_{i+1,y} 更新，其中 t_{x,y} 是转移系数，容易看出这是一个矩乘的形式，故这一部分 O(n^3 \log m)。

接下来考虑怎么求出转移系数。

第 i 层有 x 个 i \to i+1 的接口，那么就一定会有 x 个 i+1 \to i 的接口，并且交替出现，注意我们钦定在 i 这个位置已经定好了序，有一些性质：

现在 i+1 层被分成了 x+1 个块，第一个和最后一个是一个单点，其余大小为 2，考虑 i+1 层的 y 个接口在干什么事情，可以新拉两个单点组成新段，可以拉一个单点和一个段相连，或者连接两个段。

据此考虑 DP，考虑将这 x+1 个块依次加入，并决策中间是否拓展，至于那两个单点组成的联通块我们在统计答案的时候再算，设 g_{i,j,k} 表示已经加入了 i 个块，形成了 j 个块，并且剩下 k 个单点，枚举 x，则初始状态为 g_{1,1,n-2x} =1。

考虑转移，有四种情况：不管，相连，拓展 i 段右端或拓展 i+1 段左端点，都拓展，分别对应转移：

g_{i,j,k} \to g_{i+1,j+1,k} \\ g_{i,j,k} \to g_{i+1,j,k} \\ g_{i,j,k} \times 2k \to g_{i+1,j+1,k-1}\\ g_{i,j,k} \times k(k-1) \to g_{i+1,j+1,k-2}

事实上，我们可以通过状态得知当前添加了几组接口，考虑统计答案，枚举 g_{x+1,j,k}，并枚举 y 统计答案，设 w = (n-x+1)-(j+k)，这个是已经填了的接口数量，考虑我们还要拉 2(y-w) 个单点组成 p=y-w 个段，由于其余的段已经定好序了，所以只有这 p 个段需要定序，还要和这些连通块归并，然后剩下的单点也要定序和归并，所以写出来就是很大依托组合式，后面看代码吧。

相当于现在我们枚举 x 用 O(n^3) DP 求出所有的 t_{x,y}，于是做到 O(n^4 +n^3 \log m)。

好像还有什么二项式反演做法可以做到 O(n^3)，这也太强了。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
namespace Manaka_Ao{
    #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
    char buf[1<<20],*p1=buf,*p2=buf;
    inline int read(){
        int ans=0,w=1;
        char ch=getchar();
        while(ch<48||ch>57){
           if(ch=='-')w=-1;
           ch=getchar();
        }
        while(ch>=48&&ch<=57){
           ans=(ans<<1)+(ans<<3)+ch-48;
           ch=getchar();
        }
        return w*ans;
    }
    const int mod=1000000007;
    ll Pow(ll x,ll y){
        ll ans=1,push=x;
        while(y){
            if(y&1)ans=ans*push%mod;
            push=push*push%mod;
            y>>=1;
        }
        return ans;
    }
    const int N=205;
    ll P[N],inv[N];
    ll C(int x,int y){
        if(x==y||y==0)return 1;
        if(x<0||y<0||y>x)return 0;
        return P[x]*inv[y]%mod*inv[x-y]%mod;
    }
    int n,m;
    ll f[N][N];
    int g[N>>1][N>>1][N];
    ll t[N][N];
    int B=100;
    struct matrix{
        ll a[N][N];
        void clear(){memset(a,0,sizeof a);}
        void init(){
            clear();
            for(int i=0;i<=B;i++)a[i][i]=1;
        }
        friend matrix operator*(matrix x,matrix y){
            matrix res;
            res.clear();
            for(int i=0;i<=B;i++){
                for(int k=0;k<=B;k++){
                    for(int j=0;j<=B;j++){
                        res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
                    }
                }
            }
            return res;
        }
    };
    matrix ksm(matrix x,ll y){
        matrix ans,push=x;
        ans.init();
        while(y){
            if(y&1)ans=ans*push;
            push=push*push;
            y>>=1;
        }
        return ans;
    }
    void add(int &a,int b){
        a+=b;
        if(a>=mod)a-=mod;
    }
    signed main(){
        P[0]=1;for(int i=1;i<N;i++)P[i]=P[i-1]*i%mod;
        inv[N-1]=Pow(P[N-1],mod-2);for(int i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
        n=read(),m=read();
        matrix ans;
        ans.clear();
        for(int x=1;x<=n/2;x++){
            //若没有选 1，那么 1 一定是第一个
            //如果选了 1，则上接口一定是第一个，下接口一定是最后一个
            ll a=C(n-1,x)*C(n-x-1,x)%mod*P[x]%mod*P[x]%mod*P[n-2*x-1]%mod*C(n-x-1,x)%mod;//1 必须是第一个
            ll b=C(n-1,x-1)*C(n-x,x)%mod*P[x-1]%mod*P[x]%mod*P[n-2*x]%mod*C(n-x-1,x-1)%mod;//选了上或下
            ans.a[0][x]=(a+2*b)%mod;
            f[1][x]=(a+2*b)%mod;
        }
        for(int x=1;x<=n/2;x++){
            memset(g,0,sizeof g);
            g[1][1][n-2*x]=1;//内部已经有序
            for(int i=1;i<x+1;i++){
                for(int j=0;j<=i;j++){
                    for(int k=0;k<=n-2*x;k++){
                        if(!g[i][j][k])continue;
                        int now=i-(j+k)+(n-2*x);
                        add(g[i+1][j][k],g[i][j][k]);//直接连上
                        add(g[i+1][j+1][k],g[i][j][k]);
                        if(k)add(g[i+1][j+1][k-1],1ll*g[i][j][k]*k*2%mod);
                        if(k>1)add(g[i+1][j+1][k-2],1ll*g[i][j][k]*k%mod*(k-1)%mod);
                    }
                }
            }
            for(int j=1;j<=x+1;j++){//还剩这么多个联通块
                for(int k=0;k<=n;k++){//剩余离散点数量
                    if(!g[x+1][j][k])continue;
                    int now=x+1-(j+k)+(n-2*x);//已经填了这么多
                    for(int y=now;2*(y-now)<=k;y++){
                        int p=y-now;//剩余
                        ll a=C(k,p)*C(k-p,p)%mod*P[p]%mod*C(j+p-2,p)%mod*P[p]%mod*g[x+1][j][k]%mod*P[k-2*p]%mod*C(k-2*p+(j+p)-2,k-2*p)%mod;
                        //内部定序，然后选择离散点单独的点对，我们知道了所有的 y，定序过后，将剩下二元组与连通块归并，考虑剩下散点，也和联通块归并
                        t[x][y]=(t[x][y]+a)%mod;
                    }
                }
            }
        }
        matrix tmp;
        tmp.clear();
        for(int x=0;x<=n/2;x++){
            for(int y=0;y<=n/2;y++)tmp.a[x][y]=t[x][y];
        }
        ans=ans*ksm(tmp,m-1);
        cout<<ans.a[0][0]<<'\n';
        return 0;
    }
}
signed main(){
    double Stim=clock();
    Manaka_Ao::main();
    double Ttim=clock();
    cerr<<(Ttim-Stim)/1000<<'\n';
    return 0;
}