一年补一题，一题补一年（2）| [省选联考 2024] 重塑时光

· · 个人记录

题目链接

先考虑说假如我们有 k+1 个段，它们是合法的，那有多少种排列方式。其实就是有 k+1 个位置，如果有 L 个非空段，那就有 (k+1)^{\underline L} 种排列方式。

那我们现在不考虑段而考虑划分。对于一个划分 [n]=\bigsqcup\limits_{i=1}^L S_i，首先它要是合法的，在此之上有 (k+1)^{\underline L} 种它们之间的排列方式，此外它们每个内部的拓扑序数量还要乘起来。记 f_S 表示 S 的拓扑序个数，这个枚举第一个点就能 O(n2^n) 求。那么我们要求的是

\dfrac{k!}{(n+k)!}\sum_{[n] 的划分 \{S_i\}(i=1,2,\cdots,L)}[合法](k+1)^{\underline L}\prod f_{S_i}

考虑这个合法性是什么。其实就是把 S_i 缩成一个点，满足缩完之后是 DAG。考虑 DAG 计数的经典方法：枚举零出度点集进行容斥。这里的点集实际上是一些集合 \{S_i\} 的集合。换言之，设 g_{S,d} 表示考虑集合 S 里的点，所有划分为 d 个集合的合法方案中，\prod f_{S_i} 的和。那么枚举零度点集 T 有：

g_{S,d}=\sum_{\tiny \begin{array}{c}T\subseteq S\\T\neq \varnothing\\S\backslash T 到 T 没边\end{array}}\sum_{\tiny\begin{array}{c}T 的划分 \{R_i\}(i=1,2,\cdots,L)\\ R_i 之间两两没有边\end{array}}(-1)^{L-1}g_{S\backslash T,d-L}\prod f_{R_i}

设

\sum_{\tiny\begin{array}{c}T 的划分 \{R_i\}(i=1,2,\cdots,L)\\ R_i 之间两两没有边\end{array}}(-1)^{L-1}\prod f_{R_i}

为 h_{T,L}，那么 H 是容易在 O(n3^n) 内求出的，然后就可以 O(n^23^n) 求出 g 进而求出答案。这个在 CCF 数据下可以过的，不过大概率会被 n=15,m=0,k=15 卡掉。注意到固定 S,T，g 的转移是卷积形式。考虑写成多项式然后对点值转移，最后插值回去或者暴力高斯消元就可以做到 O(n3^n)。

下面是 O(n^23^n) 的代码。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,del##i##verme=int(n);i<del##i##verme;++i)
#define rep1(i,n) for(int i=1,parano##i##a=int(n);i<=parano##i##a;++i)
#define per(i,n) for(int i=int(n)-1;i>=0;--i)
#define per1(i,n) for(int i=int(n);i>=1;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define y0 LingLuo
#define y1 VividCycle
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using namespace std;
const ll mod2=1000000007;
int n,m,K,u,v;
bool ok[32768];
int to[19],fr[19];
ll fac[255],ivf[255];
ll f[33333];
ll h[16][33333],g[16][33333];
ll answer;
bool cur[33333];
int lg[333333];
int main()
{
    cin>>n>>m>>K;
    fac[0]=1;rep1(i,60)fac[i]=fac[i-1]*i%mod2;
    ivf[60]=279203279;per(i,60)ivf[i]=ivf[i+1]*(i+1)%mod2;
    rep(i,m)
    {
        cin>>u>>v;--u;--v;to[u]|=1<<v;fr[v]|=1<<u;
    }
    rep(i,n) lg[1<<i]=i;
    f[0]=1;
    rep1(i,(1<<n)-1)
    {
        rep(j,n) if((i>>j)&1) if((to[j]&i)==0) f[i]+=f[i&~(1<<j)];
        f[i]%=mod2;
    }
    h[0][0]=mod2-1;
    rep1(i,n)
    {
        rep(j,1<<n) if(h[i-1][j])
        {
            if(h[i-1][j]<0)h[i-1][j]+=mod2;
            for(int k=(j+1)|j;k<(1<<n);k=(k+1)|j)
            {
                int rest=k^j;
                if(rest==0) cur[rest]=true;
                else if((rest&(rest-1))==0) cur[rest]=((j&(to[lg[rest]]|fr[lg[rest]]))==0);
                else cur[rest]=cur[rest&(rest-1)]&&cur[rest&-rest];
                if(cur[rest])
                if((rest&-rest)==(k&-k))
                {
                    h[i][k]=(h[i][k]-h[i-1][j]*f[rest])%mod2;
                }
            }
        }
    }
    rep(j,1<<n) if(h[n][j]<0) h[n][j]+=mod2;
    g[0][0]=1;
    rep(i,n)
    {
        rep(j,1<<n) if(g[i][j])
        {
            for(int k=j;k<(1<<n);k=(k+1)|j)
            {
                int rest=k^j;
                if(rest==0) cur[rest]=true;
                else if((rest&(rest-1))==0) cur[rest]=((j&(to[lg[rest]]))==0);
                else cur[rest]=cur[rest&(rest-1)]&&cur[rest&-rest];
                if(cur[rest])
                {
                    for(int l=i+1;l<=n;++l)
                    {
                        g[l][k]=(g[l][k]+g[i][j]*h[l-i][rest])%mod2;
                    }
                }
            }
        }
    }
    rep1(i,min(K+1,n))
    {
        answer=(answer+g[i][(1<<n)-1]*ivf[K+1-i])%mod2;
    }
    cout<<answer*fac[K]%mod2*fac[K+1]%mod2*ivf[n+K]%mod2<<endl;
    return 0;
}
/* things to check
1.  int overflow or long long memory need
2.  recursion/array/binary search/dp/loop bounds
3.  precision
4.  special cases(n=1,bounds)
5.  delete debug statements
6.  initialize(especially multi-tests)
7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <=
8.  keep it simple and stupid
9.  do not delete, use // instead
10. operator priority
11. is there anything extra to output?
12. ...
*/

/* something to think about
1. greedy? dp? searching? dp with matrix/ segment tree? binary search?
2. If contains "not", why not ?????? or few affect?
*/