[BOJ 20531] 인간관계

https://www.acmicpc.net/problem/20531

20531번: 인간관계

Tag : combinatorics, prefix sum

 

문제 요약

N명의 사람을 K개의 그룹으로 분할하는 경우의 수 \(dp_{N,K}\)는 \(\sum{\binom{N}{j}*dp_{N-j,K}}\)처럼 표현할 수도 있지만 

좀 계산하기 쉬운 형태로도 나타낼 수 있다.

\(dp_{i,j}=dp_{i-1,j-1} + j \times dp_{i-1,j}\)

이 식을 토대로 계산만 해주면 된다.

 

시간복잡도 : \(O(N^2)\)

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

int N,M;
ll dp[5050][5050];
const ll MOD=1e9+7;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    cin>>N>>M;
    for(int i=1;i<=N;i++){
        dp[i][1]=1;
        for(int j=2;j<=i;j++){
            dp[i][j]=(dp[i-1][j-1]+j*dp[i-1][j]%MOD)%MOD;
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=i;j++){
            dp[i][j]=(dp[i][j]+dp[i][j-1])%MOD;
        }
    }
    vector<int>pa(N+1);iota(all(pa),0);
    int sz=N;
    function<int(int)>find=[&](int a)->int{
        if(a==pa[a])return a;
        else return pa[a]=find(pa[a]);
    };
    auto merge=[&](int a,int b)->void{
        a=find(a);b=find(b);
        if(a==b)return;
        pa[b]=a;
        sz--;
    };
    for(;M--;){
        int a,b;cin>>a>>b;
        merge(a,b);
        cout<<dp[sz][sz]<<endl;
    }
}