AtCoder Beginner Contest 310F

ABC310F

部分和 DP. \(M := 10\) とおく． \(s \subset [0,M] \) を作れる数全体とする．
今のさいころの出目 \(x\) によって場合分け．

• \(x \in [1,min(a_{i}, M)]\) の場合:
  作れる数の集合が \(t := s \cup \{y+x \ \vert \ y \in s\}\) に変わる． \(dp_{t} \text{+=} old_{s}\)．
• \(x \in (min(a_{i},M), a_{i}]\) の場合:
  サイコロの目を採用することはないので， \(s\) は変わらない． \(a_{i}\) が大きいので，まとめて遷移する．
  \(dp_{s} \text{+=} (max(0, a_{i}-m))*old_{s}\)．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  int n;

  cin >> n;

  const int m = 10;

  const int m2 = 1<<(m+1);

  vector<mint> dp(m2);

  dp[1] = 1;

  vector<int> va;

  rep(i,n) {

    int a;

    cin >> a;

    va.push_back(a);

    vector<mint> p(m2); swap(dp,p);

    rep(s,m2) {

      for (int x = 1; x <= min(m,a); x++) {

        dp[(s|s<<x)&(m2-1)] += p[s];

      }

      dp[s] += p[s]*max(0,a-m);

      // dp[s] /= a;

    }

  }

  mint ans = 0;

  rep(s,m2) if (s>>m&1) ans += dp[s];

  rep(i,n) {

    ans /= mint(va[i]);

  }

  cout << ans.val() << endl;

  return 0;

 

}