[省选联考 2024] 重塑时光

因为太弱了而感觉网上过的题解都不够详细清晰！所以写了篇题解！

估计也会成为我后面给初中的学弟学妹们讲题的题目之一，前提是没有其他人要选它

首先，肯定要将概率转为方案数

若我们已经将一个排列划分成了\(k+1\)块（有空的）且已经重新拼接成了一条新的时间线，这些块中有\(i\)个非空的，那么此时这中情况的贡献，也就是这个情况对应的原排列和切割方式的方案数为\(i!k!C_{k+1}^i\)，\(i!\)是原排列中这\(i\)组可以以任意顺序排列，\(k!\)是\(k\)刀可以以任意序列排列，\(C_{k+1}^i\)是剩下的\(k+1-i\)个空块和这\(i\)个非空块在被切割的原排列中是以任意顺序排列的，最后得到的答案再除以一个\((n+k)!\)即可

那么现在来考虑如何求出 将一个排列划分成了k+1块（有空的）且已经重新拼接成了一条新的时间线，这些块中有i个非空的的方案数，设其为\(f_i\)

先说一个很重要的点，若我们已经得到了一个\((k+1)\)段序列，且已经重新拼接成了一条新的时间线，考虑如何判断其是否合法，显然，对原图中有先后顺序要求的边连有向边\((u,v)\)，只要当前新的时间线中，每个块中不存在后面的点连向前面的点的边，并且将每个块缩成一个点，这些缩点间不存在后面的点连向前面的点的边，就是合法的

直接求肯定是不好求的，但是发现这里的限制是 恰好i个非空块，那么可以考虑容斥，先求出 至少i个非空块之类的，但是发现这个也不好弄，主要的原因就是，仅仅只是 i个非空块的限制，转移的时候无论怎样都会算重，当然，不排除\(wtcl\)不会做的可能，考虑加强限制，设\(g_{S,i}\)表示将集合\(s\)中的点分成至少\(i\)个独立块（块与块之间没有边）的方案数，这个好求，只需要借助一个\(h_S\)表示将集合\(S\)分到一个块中的所有排列的方案数，只需要满足不存在后面的点连向前面的点的边即可，这个也好求，只需要每次枚举第一个放到这个排列的第一个的点即可，那么\(g_{S,i}=\sum_{T\subseteq S} [!edge(S/T,T)\&\&!edge(T,S/T)]g_{S/T,i-1}h_{T}\)

那么将\(f_i\)也扩展成\(f_{S,i}\)，则有\(f_{S,i}=\sum_{T\subseteq S}[!edge(T,S/T)]\sum_{j=0}^i f_{S/T,i-j}g_{T,j}(-1)^{j+1}\)

直接做是\(O(3^nn^2)\)的，考虑优化，发现\(\sum_{j=0}^i\)的部分其实就是卷积的形式，直接\(ntt\)常数大，过不了，考虑另一种转为点值的形式：拉格朗日插值法

则原式可以表示为\(F_S=\sum_{T\subseteq S}[!edge(T,S/T)] F_{S/T}G_{T}\)，其中\(F_S(x)=\sum_{i=0}^n f_{S,i}x^i\)，\(G_T\)同理

因为\(n\)次的只需要\(n+1\)个不同的\(x\)值代入\(F_S(x)\)中就可以解出其它\(x\)值的\(F_S(x)\)或是\(F_S(x)\)每一项的系数，所以只需要将\(1\sim n+1\)代入，然后求出对应的\(F_S(x)\)即可

最后，\(F_S(x)\)的每一项的系数就是我们要求的\(f_{S,i}\)，所以现在只剩下如何拉格朗日插值求多项式系数

因为我们只需要\(S=(1<<n)-1\)的\(F_S(x)\)的系数，所以下文省略掉\(S\)这个下角标

若我们当前已经求得了\(n+1\)种不同\(x\)的\(F(x)\)的值，那么考虑构造\(n+1\)个多项式，设其为\(Q_i(x)\)，要求\(F(x)=\sum Q_i(x)\)，要求\(Q_i(x)=F(i)\)，那么只需要将这\(n+1\)个多项式相加就可以得到\(F(x)\)的多项式系数了，而\(Q_i(x)\)只需要按照拉格朗日插值中的方法构造即可，即\(Q_i(x)=F(i)\frac{\prod_{j=1\&\&j\neq i}^{n+1}x-j}{\prod_{j=1\&\&j\neq i}^{n+1} i-j}\)，\(F(i)\)和分母都是常数，设\(p(x)=\sum_{j=1}^{n+1}x-j\)，则分子可以表示为\(\frac{p(x)}{x-i}\)，若分子的\(x^t\)的系数为\(k_t\)，\(p(x)\)的为\(a_t\)，手模一下这个除法，可以发现\(k_t=a_t+i\times k_{t+1}\)

然后就可以了，复杂度为\(O(3^NN+2^NN^2)\)

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
void add(int &x,int y){ x+=y; if(x>=MOD) x-=MOD; if(x<0) x+=MOD; }
int ad(int x,int y){ x+=y; if(x>=MOD) x-=MOD; if(x<0) x+=MOD; return x; }
int power(int x,int y){
    int ans=1;
    for(;y;y>>=1,x=1ll*x*x%MOD) if(y&1) ans=1ll*ans*x%MOD;
    return ans;
}
int n,m,k,ans;
int vis[20],edge[1<<15],jc[40],invf[40];
int h[1<<15],g[1<<15][16];
int fp[20],fv[1<<15],gv[1<<15];
int a[20],b[20],f[20];
void Init(){
    jc[0]=1;
    for(int i=1;i<=n+k;++i) jc[i]=1ll*jc[i-1]*i%MOD;
    invf[n+k]=power(jc[n+k],MOD-2);
    for(int i=n+k-1;~i;--i) invf[i]=1ll*invf[i+1]*(i+1)%MOD;
}
int solve(int x){
    for(int s=0;s<(1<<n);++s){
        gv[s]=0;
        for(int i=0,now=1;i<=n;++i,now=1ll*now*x%MOD){
            if(i+1&1) add(gv[s],-1ll*now*g[s][i]%MOD);
            else add(gv[s],1ll*now*g[s][i]%MOD);
        }
    }
    fv[0]=1;
    for(int s=1;s<(1<<n);++s){
        fv[s]=0;
        for(int t=s;t;t=(t-1)&s) if(!(edge[t]&(s^t))) add(fv[s],1ll*fv[s-t]*gv[t]%MOD);
    }
    return fv[(1<<n)-1];
}
int main(){
    scanf("%d%d%d",&n,&m,&k),Init();
    for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),vis[u]|=(1<<v-1);
    for(int s=1;s<(1<<n);++s) for(int i=1;i<=n;++i) if(s>>i-1&1) edge[s]|=vis[i];
    h[0]=1; for(int s=1;s<(1<<n);++s) for(int i=1;i<=n;++i) if((s>>i-1&1)&&!(vis[i]&(s^(1<<i-1)))) add(h[s],h[s^(1<<i-1)]);
    g[0][0]=1;
    for(int s=1,pos;s<(1<<n);++s){
        for(int i=1;i<=n;++i) if(s>>i-1&1) pos=i;
        for(int t=s;t;t=(t-1)&s) if(!(edge[s^t]&t)&&!(edge[t]&(s^t))&&(t>>pos-1&1)) for(int i=1;i<=n;++i) add(g[s][i],1ll*g[s^t][i-1]*h[t]%MOD);
    }
    a[0]=1;
    for(int i=1;i<=n+1;++i){
        fp[i]=solve(i);
        for(int j=i;~j;--j) a[j]=ad(j?a[j-1]:0,-1ll*i*a[j]%MOD);
    }
    for(int i=1,res;i<=n+1;++i){
        res=1ll*fp[i]*invf[i-1]%MOD*invf[n+1-i]%MOD;
        if((n+1-i)&1) res=ad(0,-res);
        for(int j=0;j<=n+1;++j) b[j]=a[j];
        for(int j=n+1;j;--j) add(f[j-1],1ll*res*b[j]%MOD),add(b[j-1],1ll*i*b[j]%MOD);
    
    }
    for(int i=0;i<=k+1;++i) add(ans,1ll*f[i]*jc[k]%MOD*jc[k+1]%MOD*invf[k+1-i]%MOD);
    printf("%d\n",1ll*ans*invf[n+k]%MOD);
    return 0;
}