[bfs 트리 계층화] [DP] hihocoder Pro.1147 시공진

8547 단어 DPbfs 트리
제목 전송문
Manchery가 말한 bfs 트리의 제목이기 때문에 bfs 트리는 조상으로 돌아가는 가장자리가 존재하지 않기 때문에 bfs 트리의 점의 깊이는 뿌리 노드가 가장 짧은 길이에 이르는 것을 고려하면 한 층 한 층 DP가 있다.영fi, j, s는 DP가 i층까지 표시하고 모두 j개의 점을 사용했다. i층에 s개의 점이 있을 때의 방안수는 제목이 n개의 점 거리만 k로 요구하기 때문에 우리는 DP가 k층(영1노드는 0층)까지 가기만 하면 나머지 점은 끝없이 이어지면 된다.
f, j, s를 고려하면 f-3-1, j-3s, w에서 옮길 수 있다.
4
  • 선점
    4
  • i
    4
  • i=k층에서 n노드는 반드시 선택해야 하기 때문에 방안수는 (n-3-j+s-3-1s-3-1)

    • 4
  • 선택한 이 s개의 점은 상층의 w개의 점과 연결되어야 하고 이 s개의 점은 적어도 한 개의 변을 연결해야 한다. 그러면 총 연결의 방안 수는 (2w-3-1)s이다

    • 4
  • 이 점들은 서로 직접 연결할 수 있고 전체 방안 수는 2s×(s−1)2

    • 그래서 옮기는 건...
  • i
  • i=k→fi,j,s=fi−1,j−s,w×(n−j+s−1s−1)×(2w−1)s×2s×(s−1)2

    • 이렇게 하면 돼요.
    #include 
#include 
#include 

using namespace std;

const int N=110,P=1e9+7;

int n,k,f[N][N][N];
int fac[N],inv[N];

inline int Pow(int x,int y){
  int ret=1;
  for(;y;y>>=1,x=1LL*x*x%P) if(y&1) ret=1LL*ret*x%P;
  return ret;
}

inline int C(int x,int y){
  return 1LL*fac[x]*inv[y]%P*inv[x-y]%P;
}

inline void add(int &x,int y){
  if((x+=y)>=P) x-=P;
}

int main(){
  freopen("1.in","r",stdin);
  freopen("1.out","w",stdout);
  scanf("%d%d",&n,&k);
  fac[0]=inv[0]=inv[1]=1;
  for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%P;;
  for(int i=2;i<=n;i++) inv[i]=1LL*(P-P/i)*inv[P%i]%P;
  for(int i=1;i<=n;i++) inv[i]=1LL*inv[i]*inv[i-1]%P;
  f[0][1][1]=1;
  for(int i=1;i<=k;i++)
    for(int j=1;j<=n;j++)
      for(int s=1;s<=j;s++)
    for(int w=1;w<=j-s;w++)
      if(is],1LL*f[i-1][j-s][w]*C(n-j+s-1,s)%P*Pow(Pow(2,w)-1,s)%P*Pow(2,s*(s-1)/2)%P);
      else
        add(f[i][j][s],1LL*f[i-1][j-s][w]*C(n-j+s-1,s-1)%P*Pow(Pow(2,w)-1,s)%P*Pow(2,s*(s-1)/2)%P);
  int ans=0;
  for(int i=k+1;i<=n;i++)
    for(int j=1;j<=n;j++)
      add(ans,1LL*f[k][i][j]*Pow(2,(n-i)*(n-i-1)/2+j*(n-i))%P);
  printf("%d
    "    ,ans);
  return 0;
}
    BOJ 2579 계단 오르기
    재사용 가능한 디자인을 빠르게 생성하기 위한 CSS-in-JS 라이브러리 작성

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage