Submission #862624

#TimeUsernameProblemLanguageResultExecution timeMemory
862624AbdelmagedNourMagneti (COCI21_magneti)C++17
110 / 110
42 ms4960 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; typedef long long ll; const int N=12005,mod=(1e9)+7; ll Fact[N],inv[N]; void preprocess(){ Fact[0]=Fact[1]=inv[0]=inv[1]=1; for(int i=2;i<N;i++){ Fact[i]=i*Fact[i-1]%mod; inv[i]=mod-mod/i*inv[mod%i]%mod; } for(int i=2;i<N;i++)inv[i]=inv[i]*inv[i-1]%mod; } ll nCr(int n,int r){ return Fact[n]*inv[n-r]%mod*inv[r]%mod; } ll dp[N][55]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); preprocess(); int n,l; cin>>n>>l; int a[n+1]={}; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+n+1); dp[0][0]=1; for(int i=1;i<=n;i++){ for(int k=l;k>=1;k--){ for(int j=1;j<=i;j++){ dp[k][j]=dp[k-1][j-1]; if(k>=a[i])dp[k][j]+=dp[k-a[i]][j]*2LL*j; if(k>=(2*a[i]-1))dp[k][j]+=dp[k-(2*a[i]-1)][j+1]*j*(j+1); dp[k][j]%=mod; } } dp[0][0]=0; } ll res=0; for(int i=1;i<=l;i++)res+=dp[i][1]*nCr(n+l-i,n)%mod; cout<<(res%mod); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...