fork(14) download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int mod = 1e9 + 7;
  5. int32_t main()
  6. {
  7.     int T;
  8.     cin >> T;
  9.     while (T--)
  10.     {
  11.         int n1, n2, k1, k2;
  12.         cin >> n1 >> n2 >> k1;
  13.         k2 = k1;
  14.  
  15.         vector<vector<vector<vector<int>>>> dp(n1 + 1, vector<vector<vector<int>>>(n2 + 1, vector<vector<int>>(max(k1, k2) + 1, vector<int>(2, 0))));
  16.         dp[0][0][0][1] = 1;
  17.         dp[0][0][0][0] = 1;
  18.  
  19.         for (int i = 0; i <= n1; i++) 
  20.         {
  21.             for (int j = 0; j <= n2; j++) 
  22.             {
  23.                 for (int k = 0; k <= k2; k++)
  24.                     if (j >= k && i - 1 >= 0)
  25.                         dp[i][j][1][0] += dp[i - 1][j][k][1], dp[i][j][1][0] %= mod;
  26.  
  27.                 for (int k = 0; k <= k1; k++) 
  28.                     if (i >= k && j - 1 >= 0)
  29.                         dp[i][j][1][1] += dp[i][j - 1][k][0], dp[i][j][1][1] %= mod;
  30.  
  31.                 for (int rep = 2; rep <= k1; rep++)
  32.                 {
  33.                     if (i - 1 >= 0 && i >= rep)
  34.                         dp[i][j][rep][0] += dp[i - 1][j][rep - 1][0], dp[i][j][rep][0] %= mod;
  35.                 }
  36.                 for (int rep = 2; rep <= k2; rep++)
  37.                 {
  38.                     if (j - 1 >= 0 && j >= rep)
  39.                         dp[i][j][rep][1] += dp[i][j - 1][rep - 1][1], dp[i][j][rep][1] %= mod;
  40.                 }
  41.  
  42.             }
  43.         }
  44.  
  45.         int ans = 0;
  46.         for (int i = 0; i <= n1; i++)
  47.         {
  48.             for (int j = 0; j <= n2; j++)
  49.             {
  50.                 if (i + j == n1 + n2)
  51.                 {
  52.                     for (int k = 0; k <= max(k1, k2); k++)
  53.                     {
  54.                         ans += dp[i][j][k][0];
  55.                         ans %= mod;
  56.                         ans += dp[i][j][k][1];
  57.                         ans %= mod;
  58.                     }
  59.                 }
  60.             }
  61.         }
  62.         cout << ans << "\n";
  63.     }
  64.     return 0;
  65. }
Runtime error #stdin #stdout #stderr 0s 4188KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/A1Cldk
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!