fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - Ti20 - THPT chuyên Lương Thế Vinh
  2.  
  3. #include<bits/stdc++.h>
  4. //#include <ext/pb_ds/assoc_container.hpp>
  5. //#include <ext/pb_ds/trie_policy.hpp>
  6. //#include <ext/rope>
  7.  
  8. //#pragma GCC optimize("Ofast")
  9. //#pragma GCC optimization("unroll-loops, no-stack-protector")
  10. //#pragma GCC target("avx,avx2,fma")
  11.  
  12. //using namespace std;
  13. //using namespace __gnu_pbds;
  14. //using namespace __gnu_cxx;
  15.  
  16. #define fi first
  17. #define se second
  18. #define TASK "test"
  19. #define pb push_back
  20. #define EL cout << endl
  21. #define Ti20_ntson int main()
  22. #define in(x) cout << x << endl
  23. #define all(x) (x).begin(),(x).end()
  24. #define getbit(x, i) (((x) >> (i)) & 1)
  25. #define cntbit(x) __builtin_popcount(x)
  26. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  27. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  28. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  29.  
  30. using namespace std;
  31.  
  32. typedef long long ll;
  33. typedef vector<int> vi;
  34. typedef pair<int,int> vii;
  35. typedef unsigned long long ull;
  36. typedef vector<vector<int>> vvi;
  37.  
  38. const int N = 1e5 + 5;
  39. const int oo = INT_MAX;
  40. const int mod = 1e9 + 7;
  41. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  42. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  43.  
  44. int w, b, r, K, m, ch[303][303], dp[305][305][305][2];
  45.  
  46. inline void Add(int &u, int v) {
  47.     u += v;
  48.     if (u >= mod)
  49.         u -= mod;
  50. }
  51.  
  52. inline void Read_Input() {
  53.     cin >> w >> b >> r >> K >> m;
  54.     dp[1][0][0][0] = 1;
  55.     dp[0][1][0][1] = 1;
  56. }
  57.  
  58. inline int C(int k, int n) {
  59.     if (ch[k][n] != -1)
  60.         return ch[k][n];
  61.     if (k == 1) return n;
  62.     if (k == 0) return 1;
  63.     if (k > n) return 0;
  64.     ch[k][n] = C(k, n - 1);
  65.     Add(ch[k][n], C(k - 1, n - 1));
  66.     return ch[k][n];
  67. }
  68.  
  69. int f[305], g0[305][305], g1[305][305];
  70.  
  71. inline void Solve() {
  72.     memset(ch, -1, sizeof(ch));
  73.     /// dp[Red][Blue][Num][last]
  74.     /// Red -> last = 0
  75.     /// Blue -> last = 1
  76.     FOR(i, 0, r)
  77.         FOR(j, 0, b)
  78.             FOR(k, 0, r + b)
  79.                 FOR(t, 0, 1)
  80.                     if (dp[i][j][k][t]) {
  81.                         if (i == r && j == b) {
  82.                             Add(f[k], dp[i][j][k][t]);
  83.                             continue;
  84.                         }
  85.                         if (t == 0) {
  86.                             Add(dp[i + 1][j][k][t], dp[i][j][k][t]);
  87.                             Add(dp[i][j + 1][k + 1][1], dp[i][j][k][t]);
  88.                             continue;
  89.                         }
  90.                         if (t == 1) {
  91.                             Add(dp[i + 1][j][k + 1][0], dp[i][j][k][t]);
  92.                             Add(dp[i][j + 1][k][t], dp[i][j][k][t]);
  93.                             continue;
  94.                         }
  95.                     }
  96.  
  97.     /// phân W màu trắng ra thành các tập hợp nhóm riêng lẻ, không quá k mỗi nhóm 
  98.  
  99.     g0[0][0] = 1;
  100.     g1[0][0] = 1;
  101.     int Ans = 0;
  102.     FOR(i, 1, w)
  103.         FOR(j, 1, w)
  104.             FOR(k, 0, i - 1)
  105.                 if (i - k < K)
  106.                     Add(g1[i][j], g1[k][j - 1]);
  107.     FOR(i, 0, w)
  108.         FOR(j, 0, r + b + 1)
  109.             if (i + j > 0)
  110.                 FOR(k, 0, i)
  111.                     if (i - k < K)
  112.                         Add(g0[i][j], g0[k][j - 1]);
  113.  
  114.  
  115.     FOR(i, m, r + b) {
  116.         int u = i - m;
  117.         int v = r + b + 1 - i;
  118.         FOR(j, 0, w) {
  119.             int res = 1ll * C(u, i) * g1[j][u] % mod;
  120.             res = 1ll * res * g0[w - j][v] % mod;
  121.             res = 1ll * res * f[i] % mod;
  122.             Add(Ans, res);
  123.         }
  124.     }
  125.  
  126.     cout << Ans;
  127. }
  128.  
  129. Ti20_ntson {
  130. //    freopen(TASK".INP","r",stdin);
  131. //    freopen(TASK".OUT","w",stdout);
  132.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  133.     int T = 1;
  134.     while (T -- ) {
  135.         Read_Input();
  136.         Solve();
  137.     }
  138. }
  139.  
  140.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cuPjhL
language:
C++14 (gcc 8.3)
created:
4 days 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!