oj.uz

Submission #892381

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

const int MAXN = 1e5 + 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 <= 100000; i++)
    {
        fact[i] = 1ll * fact[i - 1] * i % MOD;
    }

    finv[100000] = Pow(fact[100000], MOD - 2);
    for (int i = 100000 - 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=1;
        long long m=l-(n-1)*a[n]-1;
        long long tmp=C(m+n, m);
        res=(fact[n]*tmp)%MOD;
        cout<<res;
        return 0;
    }

    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, gap))%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 2 ms 2652 KB Output is correct
2 Incorrect 2 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 50.0

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