Submission #1300349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300349		tte0	Magneti (COCI21_magneti)	C++20	0 / 110	3 ms	572 KiB

Main

// Author: Teoman Ata Korkmaz
#pragma GCC optimize("O3,unroll-loops,inline")
#include <bits/stdc++.h> 
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt")
#define int int_fast64_t
using namespace std;
constexpr int N=1e4+4;
constexpr int MOD=1e9+7;
///////////////////////////////////////////////////////////
int n,l,fact[N],inv_fact[N];
//int32_t dp[N][N];//partition K (i) into N (j)
vector<int> v;

inline int fp(int b,int p){
    int ans=1;
    while(p){
        if(p&1)ans=(ans*b)%MOD;
        p>>=1;
        b=(b*b)%MOD;
    }
    return ans;
}

inline int nCr(int n,int r){
    return (((fact[n]*inv_fact[r])%MOD)*inv_fact[n-r])%MOD;
}

signed main(void){
    fact[0]=1;for(int i=1;i<N;i++)fact[i]=(fact[i-1]*i)%MOD;
    for(int i=0;i<N;i++)inv_fact[i]=fp(fact[i],MOD-2);
    //cerr<<"inv_Fact: ";for(int i=0;i<5;i++)cerr<<inv_fact[i]<<" ";cerr<<endl;

    /*for(int n=0;n<5;n++){
        for(int r=0;r<n;r++){

            cerr<<"nCr("<<n<<","<<r<<")="<<nCr(n,r)<<endl;
        }
    }*/


    /*for(size_t k=0;k<5;k++){
        cerr<<"dp: ";
        for(size_t n=0;n<5;n++){
            cerr<<dp[k][n]<<" ";
        }
        cerr<<endl;
    }cerr<<endl;*/

    cin>>n>>l;  
    if(n==1){
        cout<<l<<endl;
        exit(0);
    }
    v.resize(n);
    for(auto& i:v){cin>>i;i--;}

    int range_size=0;
    for(int i=0;i<n;i++)range_size+=2*v[i]+1;

    /*for(int n=0;n<5;n++){
        for(int r=0;r<n;r++){
            cerr<<"nCr("<<n<<","<<r<<")="<<nCr(n,r)<<endl;
        }
    }*/
    
    int ans=0;
    for(int start=0;start<n;start++){
        for(int stop=0;stop<n;stop++){
            if(start==stop)continue;
            int step=l-(range_size-v[start]-v[stop]);
            if(step<0)continue;
            //cerr<<"yippe"<<endl;
            //cerr<<"fact: ";for(int i=0;i<5;i++)cerr<<fact[i]<<" ";cerr<<endl;
            //cerr<<"nCr("<<n<<","<<step<<")="<<nCr(n,step)<<endl;
            ans+=nCr(l,step);
            //cerr<<"start stop step: "<<start<<" "<<stop<<" "<<step<<endl;
            //cerr<<"ans: "<<ans<<endl;
            ans%=MOD;
        }
    }
    ans%=MOD;
    ans*=fact[n-2];
    ans%=MOD;

    cout<<ans<<endl;
}

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