P2638. 安全系统

考点

• 高精度
• 排列组合

题解

#include <bits/stdc++.h>
using namespace std;

struct Bigint {
  int len_;
  int arr_[1050];
  Bigint(int x = 0) {
    memset(arr_, 0, sizeof(arr_));
    len_ = 0;
    do {
      arr_[++len_] = x % 10;
      x /= 10;
    } while (x);
  }
  int &operator[](int x) { return arr_[x]; }
  void flatten(int len) {
    len_ = len;
    for (int i = 1; i <= len_; ++i) {
      if (arr_[i] >= 10) {
        arr_[i + 1] += arr_[i] / 10;
        arr_[i] %= 10;
      }
    }
    while (!arr_[len_] && len_) --len_;
  }
  void print() {
    for (int i = max(1, len_); i >= 1; --i) {
      cout << arr_[i];
    }
  }
} C[51][51];

Bigint operator+(Bigint a, Bigint b) {
  Bigint c;
  int len = max(a.len_, b.len_);
  for (int i = 1; i <= len; ++i) {
    c[i] += a[i] + b[i];
  }
  c.flatten(len + 1);
  return c;
}

Bigint operator*(Bigint a, Bigint b) {
  Bigint c;
  for (int i = 1; i <= a.len_; ++i) {
    for (int j = 1; j <= b.len_; ++j) {
      c[i + j - 1] += a[i] * b[j];
    }
  }
  c.flatten(a.len_ + b.len_);
  return c;
}

void f() {
  for (int i = 0; i <= 50; ++i) {
    C[i][0] = C[i][i] = Bigint(1);
    for (int j = 1; j < i; ++j) {
      C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
  }
}

int main() {
  int n, a, b;
  cin >> n >> a >> b;
  f();
  Bigint ans;
  for (int i = 0; i <= a; ++i) {
    for (int j = 0; j <= b; ++j) {
      ans = ans + (C[n + i - 1][i] * C[n + j - 1][j]);
    }
  }
  ans.print();
  return 0;
}

思路

先考虑这么一个问题：

a个球放进n个盒子，且盒子允许为空

根据插板法，每个盒子都提前塞一个进去，这样保证盒子内至少有一个

则共有n+a个元素，n+a-1个空隙；选其中n-1个空隙插入板子，可以分出n组

得到\[C_{n+a-1}^{n-1}=C_{n+a-1}^{a}\]

根据题意一个存储区可以存放任意多个0和任意多个1，说明0和1的分配是相互独立的，可以采用乘法原理

故而当0的个数为a，1的个数为b时，分配方案有\[C_{n+a-1}^{a}\times C_{n+b-1}^{b}\]

---

但是，题目还有一句话0和1可以不用全部储存，那就意味着0的个数其实是0 ~ a，1的个数其实是0 ~ b

所以需要双重循环来遍历每种搭配

---

其次，组合数过大且不能取模，所以必须采用高精度来存储