「DROI」Round 2 单图题解

Demeanor_Roy · 2023-02-19 16:55:45 · 题解

出题人题解。

第一档考虑手玩或爆搜，接下来从第二档讲起。

考虑图 G 上若存在三点 x,y,z，若满足 x \rightarrow y 有边，且 y \rightarrow z 有边，那么我们只需改变 x \rightarrow z 的有无边情况，即有边就删无边就加，就能构造出与 G 本质相同的图。那么我们似乎可以得出，图 G 是单图当且仅当其所有点入度为 0 或出度为 0。

可这是有问题的，因为存在一个反例，即两点环。不难发现若图中一两点环与外界不联通，显然也无法据此构造出与其本质相同的图。所以需分两种情况讨论。

思考如何计数，对于一个 n 个点的图。令 f(x) 表示 x 个点的单图数，g(x) 表示 x 个点不考虑两点环的单图数，t(x) 表示 x 个点只考虑两点环的单图数。显然有：

f(x)=\sum_{2i \leq x}{x \choose 2i}t(2i)g(x-2i)

先思考 t(2x) 的求解。因为 t(2x) 表示的是 2x 个点划分成 x 对两点环的方案数，我们不妨考虑一对一对选取，那么方案数就是 \prod\limits_{i=1}^x\dbinom{2x-2(i-1)}{2}。但这样做会算重，因为其实是与顺序无关的，所以再除以一个 x! 即可。化简后可得 t(x)=\prod\limits_{2i \leq n}(2i+1)。

那么 g(x) 怎么求呢？由于所有点要么无入度，要么无出度。考虑这样一种刻画：我们将所有点分为有入度和无入度两类，若前者有 y 个点，则对于前者可能有 x-y 条边，其中一条边都没有是非法的，故有 (2^{x-y}-1) 种方案，将所有点的方案合并，故此时方案数为 (2^{(x-y)}-1)^y。所以可得：

g(x)=\sum_{i=0}^{x}{x \choose i}{(2^{x-i}-1)^i}

故暴力求解可做到 O(Tn^2 \log n)。预处理 g 即可做到 O(n^2 \log n + nT)。

显然可以优化到 O(n^2 \log n + T \log n)。~~不过并不美丽也无甚价值~~ 。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=1010;

int T,n,mod,fct[N],ans[N],C[N][N];
inline int pwr(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=(LL)res*x%mod;
        x=(LL)x*x%mod;y>>=1;
    }
    return res;
}
inline void init()
{
    ans[0]=C[0][0]=C[1][0]=C[2][0]=fct[1]=1;
    for(int i=3;i<N;i++) C[i][0]=1,fct[i]=(i&1?(LL)fct[i-2]*i%mod:0);
    for(int i=1;i<N;i++)
        for(int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    for(int i=1;i<N;i++)
        for(int j=0;j<i;j++)
            ans[i]=(ans[i]+(LL)C[i][j]*pwr(pwr(2,i-j)-1,j)%mod)%mod;                
}

inline void solve()
{
    scanf("%d",&n);
    int res=ans[n];
    for(int i=2;i<=n;i+=2) res=(res+(LL)C[n][i]*fct[i-1]%mod*ans[n-i]%mod)%mod;
    printf("%d\n",res);
}
int main()
{
    scanf("%d%d",&T,&mod);
    init();
    while(T--) solve();
    return 0;
}

「DROI」Round 2 单图 题解

「DROI」Round 2 单图题解