[ARC163D] Sum of SCC 题解

题目链接

点击打开链接

题目解法

好牛的性质！！！

首先一个家喻户晓的性质是：竞赛图缩点之后是一条链
考虑从这个上面拓展出一个更优美的性质：
竞赛图的 \(scc\) 个数 \(=\) 把点集分成两个集合 \(A,B\)，满足 \(\forall u\in A,v\in B\)，\(u,v\) 之间边的方向为 \(u\to v\) 的方案数 \(-1\)

这样就容易 \(dp\) 了，令 \(f_{i,j,k}\) 表示当前加入了前 \(i\) 个点，集合 \(A\) 中有 \(j\) 个点，当前满足 \(u<v,u\to v\) 的边有 \(k\) 条的方案数
转移是简单的

• 加入集合 \(A\)，\(f_{i,j,k}\times \binom{j}{l}\Rightarrow f_{i+1,j+1,k+l}\)，\(l\in[0,j]\)
• 加入集合 \(B\)，\(f_{i,j,k}\times \binom{i-j}{l}\Rightarrow f_{i+1,j,k+j+l}\)，\(l\in [0,i-j]\)

时间复杂度 \(O(n^3m)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=32,P=998244353;
int n,m,f[N][N][N*N],C[N][N];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int main(){
    n=read(),m=read();
    C[0][0]=1;
    F(i,1,n){ C[i][0]=C[i][i]=1;F(j,1,i-1) C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;}
    f[0][0][0]=1;
    F(i,0,n-1) F(j,0,i) F(k,0,m) if(f[i][j][k]){
        //add to A
        F(l,0,j) inc(f[i+1][j+1][k+l],1ll*f[i][j][k]*C[j][l]%P);
        //add to B
        F(l,0,i-j) inc(f[i+1][j][k+j+l],1ll*f[i][j][k]*C[i-j][l]%P);
    }
    int ans=0;
    F(i,1,n) inc(ans,f[n][i][m]);
    printf("%d\n",ans);
    return 0;
}