NC23413 小A买彩票

题目地址：

https://ac.nowcoder.com/acm/problem/23413

基本思路：

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 200;
int n;
int dp[35][210];
signed main() {
  IO;
  cin >> n;
  mset(dp, 0);
  dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = 1;
  rep(i, 2, n) {
    for (int j = i * 4; j >= 0; j--) {//买i张彩票，最高中奖金额就是i*4了;
      if (j - 1 >= 0) dp[i][j] += dp[i - 1][j - 1];
      if (j - 2 >= 0) dp[i][j] += dp[i - 1][j - 2];
      if (j - 3 >= 0) dp[i][j] += dp[i - 1][j - 3];
      if (j - 4 >= 0) dp[i][j] += dp[i - 1][j - 4];
    }
  }
  int all = 0, can = 0;
  for (int j = 0; j <= n * 4; j++) {
    all += dp[n][j];//所有可能情况;
    if (j >= 3 * n) can += dp[n][j];//不亏本的情况;
  }
  if (all == can) cout << "1/1" << '\n';
  else if (all == 0) cout << "0/1" << '\n';
  else {
    int k = __gcd(all, can);
    cout << can / k << '/' << all / k << '\n';
  }
  return 0;
}