oj.uz

Submission #851863

# Submission time Handle Problem Language Result Execution time Memory
851863 2023-09-20T17:30:24 Z vjudge1 Magneti (COCI21_magneti) C++17
0 / 110
 198 ms 4212 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define lim 1000000
#define till 1000001
// # of primes till 1e6 = 7e4
using namespace std;
using pii = array<int,2>;
const int mod=1000000007ll;

int divy[1001];

int expo(int a,int b){
    int ans=1;
    while(b){
        if(b&1){
            ans*=a;
            ans%=mod;
        }
        a*=a;
        a%=mod;
        b>>=1;
    }
    return ans;
}

int comb(int a,int b){
    int ans=1;
    for(int i=0;i<b;i++){
        ans*=a-i;
        ans%=mod;
    }
    for(int i=1;i<=b;i++){
        ans*=divy[i];
        ans%=mod;
    }
    return ans;
}

int dist[10001][50];
int fact[10001];

void solve(){
    int n,l;
    cin>>n>>l;
    fact[0]=1;
    for(int i=1;i<1001;i++){
        fact[i]=fact[i-1]*i;
        fact[i]%=mod;
        divy[i]=expo(i,mod-2);
    }
    for(int i=0;i<10001;i++){
        for(int j=1;j<50;j++){
            dist[i][j]=comb(i+j-1,j-1);
        }
    }
    int a[n];
    int tot=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i]--;
        tot+=a[i]*2+1;
    }
    if(n==1){
        cout<<l<<"\n";
        return;
    }
    int ans=0;
    for(int b=0;b<n;b++){
        for(int e=0;e<n;e++){
            if(b!=e){
                //cerr<<b<<" "<<e<<"\n";
                for(int d=l;max(a[b],a[e])<d;d--){
                    int cur=d-tot+a[b]+a[e];
                    if(cur<0){
                        break;
                    }
                    int toad=(fact[n-2]*dist[cur][n-1])%mod;
                    toad*=l-d+1;
                    toad%=mod;
                    ans+=toad;
                    //cerr<<cur<<" "<<dist[cur][n-1]<<" "<<(fact[n-2]*dist[cur][n-1])%mod<<"\n";
                    ans%=mod;
                }
            }
        }
    }
    cout<<ans<<"\n";
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 4212 KB Output is correct
2 Correct 93 ms 4180 KB Output is correct
3 Incorrect 97 ms 4152 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 4212 KB Output is correct
2 Correct 93 ms 4180 KB Output is correct
3 Incorrect 97 ms 4152 KB Output isn't correct
4 Halted 0 ms 0 KB -