ARC163D

ARC163D Sum of SCC

Description

设 表示竞赛图 中的强连通分量数量。计算所有下列条件的 的 之和：

• 有 个点。
• 所有边 中恰好有有 条边满足 。

答案对 取模。

。

Sol

竞赛图缩点之后必定可以划分成两个集合 使 中任意两点 都存在边 。

那么任意一个竞赛图的权值就是把图中元素分为 两个集合满足上述条件的方案数 。

定义 表示前 个点中 个点被分在了集合 且恰好有 条边从小编号结点指向大编号结点的方案数。

则很容易写出转移： 时间复杂度 。

Code

#include<bits/stdc++.h>
#define int long long
const int N=35;
const int M=505;
const int Mod=998244353;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
int f[N][N][M];
int n,m;
int fac[M],inv[M];
int ksm(int x,int y){
    int ans=1;
    for(;y;y>>=1,x=x*x%Mod)if(y&1)ans=ans*x%Mod;
    return ans;
}
void init(){
    fac[0]=inv[0]=1;
    for(int i=1;i<M;++i)fac[i]=fac[i-1]*i%Mod,inv[i]=ksm(fac[i],Mod-2);
}
int C(int x,int y){return x<y||x<0||y<0?0:fac[x]*inv[y]%Mod*inv[x-y]%Mod;}
signed main(){
    n=read();m=read();
    init();
    f[0][0][0]=1;
    for(int i=0;i<n;++i)
        for(int j=0;j<=i;++j)
            for(int k=0;k<=m;++k){
                for(int l=0;l<=j;++l)(f[i+1][j+1][k+l]+=f[i][j][k]*C(j,l))%=Mod;
                for(int l=0;l<=i-j;++l)(f[i+1][j][k+l+j]+=f[i][j][k]*C(i-j,l))%=Mod;
            }
    int ans=0;
    for(int i=1;i<=n;++i)(ans+=f[n][i][m])%=Mod;
    printf("%lld\n",ans);
    return 0;
}