Submission #659524

#	Time	Username	Problem	Language	Result	Execution time	Memory
659524		tibinyte	Magneti (COCI21_magneti)	C++14	20 / 110	1098 ms	12168 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int32_t MOD = 1e9 + 7;
struct modint
{
    int32_t value;
    modint() = default;
    modint(int32_t value_) : value(value_ % MOD) {}
    modint(int64_t value_) : value(value_ % MOD) {}
    inline modint operator+(modint other) const
    {
        int32_t c = this->value + other.value;
        return modint(c >= MOD ? c - MOD : c);
    }
    inline modint operator-(modint other) const
    {
        int32_t c = this->value - other.value;
        return modint(c < 0 ? c + MOD : c);
    }
    inline modint operator*(modint other) const
    {
        int32_t c = (int64_t)this->value * other.value % MOD;
        return modint(c < 0 ? c + MOD : c);
    }
    inline modint &operator+=(modint other)
    {
        this->value += other.value;
        if (this->value >= MOD)
            this->value -= MOD;
        return *this;
    }
    inline modint &operator-=(modint other)
    {
        this->value -= other.value;
        if (this->value < 0)
            this->value += MOD;
        return *this;
    }
    inline modint &operator*=(modint other)
    {
        this->value = (int64_t)this->value * other.value % MOD;
        if (this->value < 0)
            this->value += MOD;
        return *this;
    }
    inline modint operator-() const { return modint(this->value ? MOD - this->value : 0); }
    modint pow(int32_t k) const
    {
        modint x = *this, y = 1;
        for (; k; k >>= 1)
        {
            if (k & 1)
                y *= x;
            x *= x;
        }
        return y;
    }
    modint inv() const { return pow(MOD - 2); } // MOD must be a prime
    inline modint operator/(modint other) const { return *this * other.inv(); }
    inline modint operator/=(modint other) { return *this *= other.inv(); }
    inline bool operator==(modint other) const { return value == other.value; }
    inline bool operator!=(modint other) const { return value != other.value; }
    inline bool operator<(modint other) const { return value < other.value; }
    inline bool operator>(modint other) const { return value > other.value; }
};
modint operator*(int64_t value, modint n) { return modint(value) * n; }
modint operator*(int32_t value, modint n) { return modint(value) * n; }
istream &operator>>(istream &in, modint &n) { return in >> n.value; }
ostream &operator<<(ostream &out, modint n) { return out << n.value; }
struct combi
{
    int n;
    vector<modint> facts, finvs, invs;
    combi(int _n) : n(_n), facts(_n), finvs(_n), invs(_n)
    {
        facts[0] = finvs[0] = 1;
        invs[1] = 1;
        for (int i = 2; i < n; i++)
            invs[i] = invs[MOD % i] * (-MOD / i);
        for (int i = 1; i < n; i++)
        {
            facts[i] = facts[i - 1] * i;
            finvs[i] = finvs[i - 1] * invs[i];
        }
    }
    inline modint fact(int n) { return facts[n]; }
    inline modint finv(int n) { return finvs[n]; }
    inline modint inv(int n) { return invs[n]; }
    inline modint ncr(int n, int k) { return n < k or k < 0 ? 0 : facts[n] * finvs[k] * finvs[n - k]; }
    inline modint aranj(int n, int k) { return ncr(n, k) * facts[k]; }
    inline modint sb(int n, int k) { return ncr(n + k - 1, n); };
};
combi C(1e6 + 1);
int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, l;
    cin >> n >> l;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    vector<int> p(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        p[i] = i;
    }
    modint ans = 0;
    do
    {
        vector<int> b(n + 1);
        for (int i = 1; i <= n; ++i)
        {
            b[i] = a[p[i]];
        }
        int sum = 1;
        for (int i = 2; i <= n; ++i)
        {
            sum += max(b[i], b[i - 1]);
        }
        ans += C.sb(l - sum, n + 1);
    } while (next_permutation(p.begin() + 1, p.end()));
    cout << ans;
}

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