oj.uz

Submission #892358

# Submission time Handle Problem Language Result Execution time Memory
892358 2023-12-25T09:09:55 Z vjudge1 Magneti (COCI21_magneti) C++17
0 / 110
 1000 ms 158576 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 1e7 + 5;
const int MOD = 1e9 + 7;

typedef pair<long long, int> li;

int n, a[MAXN], fact[MAXN], finv[MAXN], l;
bool ok=1;
vector<li> v;

int Pow(int a, int b)
{
    if (b == 0) return 1;
    int ret = Pow(a, b / 2);
    ret = 1ll * ret * ret % MOD;
    if (b & 1) ret = 1ll * ret * a % MOD;
    return ret;
}

int C(int n, int k)
{
    return (1ll * fact[n] * finv[n - k] % MOD) * finv[k] % MOD;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    fact[0] = 1;
    for (int i = 1; i <= 1e7; i++)
    {
        fact[i] = 1ll * fact[i - 1] * i % MOD;
    }

    finv[10000000] = Pow(fact[10000000], MOD - 2);
    for (int i = 1e7 - 1; i >= 0; i--)
    {
        finv[i] = 1ll * finv[i + 1] * (i + 1) % MOD;
    }

    cin>>n>>l;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
        if(i>=2) if(a[i]!=a[i-1]) ok=0;
        v.push_back({a[i], i});
    }

    if(ok==1)
    {
        long long res=fact[n];
        long long m=l-(n-1)*a[1]-1+n;
        long long tmp=C(m, n);
        res=(res*tmp)%MOD;
        cout<<res;
        return 0;
    }

    sort(v.begin(), v.end());
    int res=0;
    do
    {
        int gap=l-n;
        for(int i=1; i<n; i++)
        {
            gap-=max({v[i-1].first-1, v[i].first-1});
        }
        res=(res+C(n+gap, n))%MOD;
    }
    while(next_permutation(v.begin(), v.end()));
    cout<<res;
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 158476 KB Output is correct
2 Incorrect 147 ms 158576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 158392 KB Output is correct
2 Correct 145 ms 158556 KB Output is correct
3 Correct 208 ms 158548 KB Output is correct
4 Correct 144 ms 158548 KB Output is correct
5 Incorrect 206 ms 158544 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 158544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 158476 KB Output is correct
2 Incorrect 147 ms 158576 KB Output isn't correct
3 Halted 0 ms 0 KB -