mickypinata

USACO-T031: Cow Pedigrees

Dec 2nd, 2021
600
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: nocows
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. const int N = 200 + 5;
  11. const int K = 100 + 5;
  12. const int MD = 9901;
  13.  
  14. int dp[N][K];
  15.  
  16. int main(){
  17.     freopen("nocows.in", "r", stdin);
  18.     freopen("nocows.out", "w", stdout);
  19.  
  20.     int n, depth;
  21.     scanf("%d%d", &n, &depth);
  22.     if(n % 2 == 0 || n < 2 * depth - 1){
  23.         cout << "0\n";
  24.         fclose(stdin);
  25.         fclose(stdout);
  26.         return 0;
  27.     }
  28.     dp[1][1] = 1;
  29.     for(int d = 2; d <= depth; ++d){
  30.         for(int i = 2 * d - 1; i <= n; i += 2){
  31.             int sum = 0;
  32.             for(int l = 1; l <= i / 2; l += 2){
  33.                 int r = i - l - 1;
  34.                 for(int j = 1; j < d - 1; ++j){
  35.                     if(l != r){
  36.                         sum = (sum + 2 * dp[l][d - 1] * dp[r][j] + 2 * dp[l][j] * dp[r][d - 1]) % MD;
  37.                     } else {
  38.                         sum = (sum + dp[l][d - 1] * dp[r][j] + dp[l][j] * dp[r][d - 1]) % MD;
  39.                     }
  40.                 }
  41.                 if(l != r){
  42.                     sum = (sum + 2 * dp[l][d - 1] * dp[r][d - 1]) % MD;
  43.                 } else {
  44.                     sum = (sum + dp[l][d - 1] * dp[r][d - 1]) % MD;
  45.                 }
  46.             }
  47.             dp[i][d] = sum;
  48.         }
  49.     }
  50.     cout << dp[n][depth] << '\n';
  51.  
  52.     fclose(stdin);
  53.     fclose(stdout);
  54.     return 0;
  55. }
  56.  
RAW Paste Data