NC23413 小A买彩票

题目地址：

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

基本思路：

要计算不亏本的概率，那么很基本的我们考虑将买 $n$ 张彩票所有可能的最终中奖金额和每个中奖金额的次数给记录，那么不亏本的情况次数去除以所有中奖情况次数就是不亏本的概率了。

那么如何求所有的可能中奖金额和次数，考虑一个简单的 $dp$ ，设 $dp[i][j]$ 表示买 $i$ 张彩票，中奖金额为 $j$ 的情况次数，那么可以得到转移方程: $dp[i][j] = \sum_{k = 1}^{4}dp[i-1][j-k]$ 。最终获奖金额在 $3*n$ 以上的就是不亏本的了，所以最终答案就是: $\frac{\sum_{i = 3*n}^{n*4} dp[n][i]}{\sum_{i = 0}^{n*4} dp[n][i]}$ 上下除以 $gcd$ 化简就是答案了。

参考代码：

#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;
}