Submission #851863

#	Time	Username	Problem	Language	Result	Execution time	Memory
851863		vjudge1	Magneti (COCI21_magneti)	C++17	0 / 110	198 ms	4212 KiB

Main

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 50