이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
//#define DEBUG
void setIO(const string &name) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin.exceptions(istream::failbit);
#ifdef LOCAL
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
freopen((name + ".out").c_str(), "w", stderr);
#endif
}
template<typename T>
T mod_inv_in_range(T a, T m) {
// assert(0 <= a && a < m);
T x = a, y = m;
T vx = 1, vy = 0;
while (x) {
T k = y / x;
y %= x;
vy -= k * vx;
std::swap(x, y);
std::swap(vx, vy);
}
assert(y == 1);
return vy < 0 ? m + vy : vy;
}
template<int MOD_>
struct modnum {
static constexpr int MOD = MOD_;
static_assert(MOD_ > 0, "MOD must be positive");
private:
using ll = long long;
int v;
public:
modnum() : v(0) {}
modnum(ll v_) : v(int(v_ % MOD)) {
if (v < 0) v += MOD;
}
explicit operator int() const { return v; }
friend std::ostream &operator<<(std::ostream &out, const modnum &n) { return out << int(n); }
friend std::istream &operator>>(std::istream &in, modnum &n) {
ll v_;
in >> v_;
n = modnum(v_);
return in;
}
friend bool operator==(const modnum &a, const modnum &b) { return a.v == b.v; }
friend bool operator!=(const modnum &a, const modnum &b) { return a.v != b.v; }
modnum inv() const {
modnum res;
res.v = mod_inv_in_range(v, MOD);
return res;
}
friend modnum inv(const modnum &m) { return m.inv(); }
modnum neg() const {
modnum res;
res.v = v ? MOD - v : 0;
return res;
}
friend modnum neg(const modnum &m) { return m.neg(); }
modnum operator-() const {
return neg();
}
modnum operator+() const {
return modnum(*this);
}
modnum &operator++() {
v++;
if (v == MOD) v = 0;
return *this;
}
modnum &operator--() {
if (v == 0) v = MOD;
v--;
return *this;
}
modnum &operator+=(const modnum &o) {
v -= MOD - o.v;
v = (v < 0) ? v + MOD : v;
return *this;
}
modnum &operator-=(const modnum &o) {
v -= o.v;
v = (v < 0) ? v + MOD : v;
return *this;
}
modnum &operator*=(const modnum &o) {
v = int(ll(v) * ll(o.v) % MOD);
return *this;
}
modnum &operator/=(const modnum &o) {
return *this *= o.inv();
}
friend modnum operator++(modnum &a, int) {
modnum r = a;
++a;
return r;
}
friend modnum operator--(modnum &a, int) {
modnum r = a;
--a;
return r;
}
friend modnum operator+(const modnum &a, const modnum &b) { return modnum(a) += b; }
friend modnum operator-(const modnum &a, const modnum &b) { return modnum(a) -= b; }
friend modnum operator*(const modnum &a, const modnum &b) { return modnum(a) *= b; }
friend modnum operator/(const modnum &a, const modnum &b) { return modnum(a) /= b; }
};
const int inf = 0x3f3f3f3f, mod = 1e9 + 7, maxn = 105, maxl = 1005;
const long long INFL = 0x3f3f3f3f3f3f3f3f;
modnum<mod> dp[maxn][maxn][maxl][3];
/*
dp[i][j][k][l] :
i - number of numbers placed
j - number of connected components
k - total sum currently (filling empty spaces with a_{i} (0-indexed)
l - number of endpoints that are filled
*/
int main() {
setIO("1");
int n, l;
cin >> n >> l;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (n == 1) {
cout << 1 << "\n";
return 0;
}
sort(a.begin(), a.end());
a.push_back(10000); // inf
if (a[1] - a[0] <= l) {
dp[1][1][a[1] - a[0]][1] = 2; //fill a[0] at one of the endpoints, there are 2 endpoints to fill.
}
if (2 * (a[1] - a[0]) <= l) {
dp[1][1][2 * (a[1] - a[0])][0] = 1; //fill a[0] in the middle, positions doesn't matter.
}
for (int i = 1; i < n; i++) {
int diff = a[i + 1] - a[i]; //this thing is "INF" if i = n - 1.
for (int j = 1; j <= i; j++) {
for (int k = 0; k <= l; k++) {
for (int z = 0; z < 3; z++) {
modnum<mod> cur = dp[i][j][k][z];
if (cur == 0) continue; //this value does not exist
//First, we try to fill one of the ends
int new_k = k + diff * (2 * j - z - 1); //there are 2*j - z - 1 positions that we're supposed to "upgrade" (-1 because one of the positions is merged with the endpoints after this move)
if (i == n - 1) {
assert(z >= 1);
}
if (z < 2 && new_k <= l) {
if (i == n - 1) {
dp[i + 1][j][new_k][z + 1] += cur * (2 - z) * j; //we have j con. comp. to choose to merge with
} else if (z == 0 || j > 1) //otherwise this coincides with i == n - 1
{
dp[i + 1][j][new_k][z + 1] += cur * (2 - z) * (j - z); //can only merge with the con comp. that are not connected to ends.
}
if (k + diff * (2 * j - z + 1) <= l) //now we create a new cc.
{
dp[i + 1][j + 1][k + diff * (2 * j - z + 1)][z + 1] += cur * (2 - z); //we can choose one of the ends to create
}
}
//Next, we dont fill the ends.
//Part 1 : Create new cc
new_k = k + diff * (2 * j - z + 2);
if (new_k <= l) //2 new positions to "upgrade"
{
dp[i + 1][j + 1][new_k][z] += cur; //nothing new happens
}
//Part 2 : Stick to one cc
new_k = k + diff * (2 * j - z);
if (new_k <= l) //no new positions to "upgrade"
{
dp[i + 1][j][new_k][z] += cur * (2 * j - z); //we can merge in 2*j - z possible positions
}
//Part 3 : Merge two ccs together
new_k = k + diff * (2 * j - z - 2);
if ((new_k <= l) && (j >= 2) && (i == n - 1 || j > 2 || z < 2)) {
if (z == 0) {
dp[i + 1][j - 1][new_k][z] += cur * j * (j - 1); //there are jP2 possible merges
}
if (z == 1) {
dp[i + 1][j - 1][new_k][z] += cur * (j - 1) * (j - 1); //there are (j-1)P2+(j-1) merges
}
if (z == 2) {
if (i == n - 1) {
dp[i + 1][j - 1][new_k][z] += cur; //there's only 1 place it can go.
} else {
dp[i + 1][j - 1][new_k][z] += cur * (j - 2) * (j - 1); //there're (j-2)P2 + 2(j-2) possiblilities
}
}
}
}
}
}
}
modnum<mod> answer = 0;
for (int i = 0; i <= l; i++) {
answer += dp[n][1][i][2]; //sum the dp values for all possible sums
}
cout << answer << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |