낙곡 P1472 젖소 가보 Cow Pedigrees

제목 설명
농민 존은 새 젖소 한 무리를 사려고 한다.이 새로운 젖소군에서, 모든 어머니의 젖소는 두 마리의 작은 젖소를 낳는다.이 젖소 사이의 관계는 두 갈래 나무로 표시할 수 있다.이 두 갈래 나무는 모두 N개의 노드가 있다(3<=N<200).이 두 갈래 나무들은 다음과 같은 성질을 가지고 있다.
각 노드의 도는 0 또는 2이다.도는 이 노드의 아이의 수이다.
나무의 높이는 K(1얼마나 다른 가보 구조가 있습니까?만약 한 가보의 나무 구조가 다른 가보와 다르다면, 이 두 가보는 다르다.출력 가능한 스펙트럼 나무의 개수는 9901의 여수로 나눈다.출력 형식 입력 형식:
두 공백이 분리된 정수, N과 K.
출력 형식:
가능한 가보수의 개수를 9901의 여수로 나누는 정수
출력 샘플 입력 샘플 #1:
5 3
출력 샘플 #1:
이
설명
번역 NOCOW
USACO 2.3
[분석] 이 문제는 어려워... 게이지 방정식이 이상해... 고개 숙여.
[코드]

#include
#include
#include
#include
#define ll long long
#define M(a) memset(a,0,sizeof a)
#define fo(i,j,k) for(register int i=j;i<=k;i++)
using namespace std;
const int mod=9901; 
int dp[205][105],s[205][105];
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    if(n%2==0) {printf("0
");return 0;}
    dp[1][1]=s[0][0]=1;
    fo(i,1,m) s[1][i]=s[0][i]=1;   //∵ * , ， 1 
    fo(i,1,n)  //  
    {
        fo(j,1,m)
          for(int k=1;k<=i-1;k+=2)
          {
              dp[i][j]=(dp[i][j]+dp[k][j-1]*s[i-k-1][j-2])%mod;  // j-1，  
              dp[i][j]=(dp[i][j]+s[k][j-2]*dp[i-k-1][j-1])%mod;  //  
              dp[i][j]=(dp[i][j]+dp[k][j-1]*dp[i-k-1][j-1])%mod;  // j-1 
          }
        fo(k,1,m) s[i][k]=(s[i][k-1]+dp[i][k])%mod;
    }
    printf("%d
",dp[n][m]);
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

【bzoj3611】 대공정 허수

이것은 아마도 매우 나체된 허수일 것이다... (최근에 트리 dp의 귀속 형식을 dfs 서열에 따라 정렬한 후 거꾸로 하는 작업이 빨라지는 것을 발견했습니다!! O(NlogN) 우선 관건이 되는 허수를 만들어라. 허...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

낙곡 P1472 젖소 가보 Cow Pedigrees

좋은 웹페이지 즐겨찾기