CP Lang
24 lines0.3 spec// coci21c2p4 Magneti: place magnets on l slots so neighbours keep their distance. Insert magnets
// largest radius first into a set of components (connected-component DP): a magnet starts,
// extends or joins components, and `ends` counts whether the two line ends are already taken.
// `used` is the length forced so far; the leftover free slots are spread by stars and bars.
type Z = Mod<1e9 + 7>
let (n, l) = read<(1..=50, 1..=1e4)>()
let r = read<[n]1..=1e4>().sorted(by: desc)
let comb = Comb<Z>(l + n)
domain State = (comps: 0..=n, used: 0..l, ends: 0..=2)
@memo(array)
fn ways(i: 0..=n, st: State) -> Z:
let (c, u, e) = st
if i == n:
return Z(Int(c == 1 and u == l - 1 and e == 0))
fn go(dc: Int, du: Int, de: Int) -> Z =
State.at((c + dc, u + du, e + de)).map(t => ways(i + 1, t)) ?? 0
let s = r[i]
var total = (c - 1 + e) * go(1, 2 * s, 0) + e * go(1, s, -1)
if c >= 1:
total += (2 * c - 2 + e) * go(0, s, 0) + e * go(0, 0, -1) + (c - 1) * go(-1, 0, 0)
total
print(if n == 1: l else: (0..l).sum(of: u => ways(0, State((0, u, 2))) * comb.choose(u + n, n)))
Accepted C++
145 lines · 11.43 s on the judge#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
<< ": "; \
dbgh(__VA_ARGS__)
#else
#define cerr \
if (false) \
cerr
#define dbg(...) 1412
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())
const long mod = 1e9 + 7;
long bpow(long base, long exp) {
long ans = 1;
while (exp) {
if (exp & 1) {
ans = (ans * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}
return ans;
}
long inv(long x) {
return bpow(x, mod - 2);
}
const int maxf = 1e6;
long fact[maxf + 1], ifact[maxf + 1];
void pcomp() {
fact[0] = ifact[0] = 1;
for (int i = 1; i <= maxf; i++) {
fact[i] = (fact[i - 1] * i) % mod;
ifact[i] = inv(fact[i]);
}
}
long choose(int n, int k) {
if (n >= 0 && k >= 0 && n - k >= 0) {
return fact[n] * ifact[k] % mod * ifact[n - k] % mod;
}
return 0;
}
const int maxn = 55, maxl = 1e4 + 5;
long dp[2][maxn][maxl][3];
void solve() {
int n, l;
cin >> n >> l;
if (n == 1) {
cout << l << endl;
return;
}
int arr[n];
for (auto& a : arr) {
cin >> a;
}
sort(arr, arr + n, greater<>());
int ci = 0, pi = 1;
dp[ci][1][l - 1][0] = 1;
for (int i = n - 1; i >= 0; i--) {
swap(ci, pi);
memset(dp[ci], 0, sizeof(dp[ci]));
for (int j = 0; j <= n; j++) {
for (int k = 0; k < l; k++) {
for (int e = 0; e <= 2; e++) {
auto gdp = [&](int nj, int nk, int ne) -> long {
nj += j;
nk += k;
ne += e;
if (0 <= nj && 0 <= nk && nk < l && 0 <= ne) {
return dp[pi][nj][nk][ne];
}
return 0;
};
long& cdp = dp[ci][j][k][e];
// create component
cdp += (j - 1 + e) * gdp(+1, 2 * arr[i], 0);
// append to component
if (j) {
cdp += (2 * j - 2 + e) * gdp(0, arr[i], 0);
}
// merge component
if (j >= 2) {
cdp += (j - 1) * gdp(-1, 0, 0);
}
// add left / right
// use existing
if (j) {
cdp += e * gdp(0, 0, -1);
}
// create new
cdp += e * gdp(+1, arr[i], -1);
cdp %= mod;
}
}
}
}
long ans = 0;
for (int i = 0; i < l; i++) {
dbg(i, dp[ci][0][i][2]);
ans = (ans + dp[ci][0][i][2] * choose(i + n, n)) % mod;
}
ans %= mod;
cout << ans << endl;
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cin.exceptions(ios::failbit);
pcomp();
int t = 1;
// cin >> t;
for (int _ = 1; _ <= t; _++) {
dbg(_);
// cout << "Case #" << _ << ": ";
solve();
}
}