제출 #1126863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126863		zNatsumi	Magneti (COCI21_magneti)	C++20	110 / 110	190 ms	100620 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
using ii = pair<int, int>;
using tp = tuple<int, int, int>;

const int N = 55, L = 1e4 + 5, mod = 1e9 + 7;

int n, l, r[N], dp[N][N][L], fac[N + L], ifac[N + L];

void add(int &x, const int y){
  x += y;
  if(x >= mod) x -= mod;
  if(x < 0) x += mod;
}

int power(int x, int y){
  int res = 1;
  for(; y; y /= 2, x = x * x % mod) if(y & 1) res = res * x % mod;
  return res;
}

int Ckn(int k, int n){ return k > n ? 0 : 1LL * (fac[n] * ifac[n - k]) % mod * ifac[k] % mod; }
int Euler(int n, int m){ return 1LL * Ckn(m - 1, n + m - 1); } // chia n keo cho m nguoi

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n >> l;
  for(int i = 1; i <= n; i++) cin >> r[i];

  sort(r + 1, r + n + 1);

  dp[1][1][1] = 1;
  for(int i = 1; i < n; i++)
    for(int j = 1; j <= i; j++)
      for(int d = 1; d <= l; d++){
        add(dp[i + 1][j + 1][d + 1], (j + 1) * dp[i][j][d] % mod);
        if(d + r[i + 1] <= l) add(dp[i + 1][j][d + r[i + 1]], 2LL * j * dp[i][j][d] % mod);
        if(j > 1 && d + 2 * r[i + 1] - 1 <= l) add(dp[i + 1][j - 1][d + 2 * r[i + 1] - 1], (j - 1) * dp[i][j][d] % mod);
      }

  fac[0] = 1;
  for(int i = 1; i <= l + n; i++) fac[i] = 1LL * fac[i - 1] * i % mod;
  ifac[l + n] = power(fac[l + n], mod - 2);
  for(int i = l + n - 1; i >= 0; i--) ifac[i] = 1LL * ifac[i + 1] * (i + 1) % mod;

  int res = 0;
  for(int d = 1; d <= l; d++) add(res, 1LL * dp[n][1][d] * Euler(l - d, n + 1) % mod);
  cout << res << "\n";

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50