#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n"
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
constexpr int MOD = (int) 1e9 + 7;
int add(int a,int b){
if(a+b>=MOD) return a+b-MOD;
return a+b;
}
int mult(int a,int b){
if(a*b>=MOD) return (a*b)%MOD;
return a*b;
}
int fast(int a,int b){
if(b==0) return 1;
int res=fast(a,b/2);
res=mult(res,res);
if(b&1) res=mult(res,a);
return res;
}
void solve(){
int n,l;
cin >> n >> l;
vector<int> ar;
int fact[1005];
int inv_fact[1005];
fact[0]=1;
for(int i=1;i<1005;i++) fact[i]=mult(i,fact[i-1]);
inv_fact[1004]=fast(fact[1004],MOD-2);
for(int i=1003;i>=0;i--) inv_fact[i]=mult(inv_fact[i+1],i+1);
for(int i=1;i<=n;i++){
int a;
cin >> a;
ar.pb(a);
}
if(n==1){
cout << l << endl;
return;
}
sort(all(ar));
reverse(all(ar));
int dp[n+6][l+6][4];
int ndp[n+6][l+6][4];
memset(dp,0,sizeof(dp));
memset(ndp,0,sizeof(ndp));
dp[0][0][0]=1;
for(int i=0;i<n;i++){
// merge
for(int j=2;j<=n;j++){
for(int x=0;x<l;x++){
for(int fl=0;fl<=2;fl++){
ndp[j-1][x+1][fl]=add(ndp[j-1][x+1][fl],mult(j-1,dp[j][x][fl]));
}
}
}
// extend
for(int j=1;j<=n;j++){
for(int x=0;x<=l;x++){
for(int fl=0;fl<=2;fl++){
if(x+ar[i]<=l) ndp[j][x+ar[i]][fl]=add(ndp[j][x+ar[i]][fl],mult(2*j-fl,dp[j][x][fl]));
if(fl+1<=2 && x+1<=l) ndp[j][x+1][fl+1]=add(ndp[j][x+1][fl+1],mult(2-fl,dp[j][x][fl]));
}
}
}
// create1
for(int j=0;j<n;j++){
for(int x=0;x+2*ar[i]-1<=l;x++){
for(int fl=0;fl<=2;fl++){
ndp[j+1][x+2*ar[i]-1][fl]=add(ndp[j+1][x+2*ar[i]-1][fl],mult(j+1-fl,dp[j][x][fl]));
}
}
}
// create2
for(int j=0;j<n;j++){
for(int x=0;x+ar[i]<=l;x++){
for(int fl=0;fl<2;fl++){
ndp[j+1][x+ar[i]][fl+1]=add(ndp[j+1][x+ar[i]][fl+1],mult(2-fl,dp[j][x][fl]));
}
}
}
//swap values
memset(dp,0,sizeof(dp));
for(int j=0;j<=n;j++)
for(int x=0;x<=l;x++)
for(int fl=0;fl<=2;fl++)
dp[j][x][fl]=ndp[j][x][fl];
memset(ndp,0,sizeof(ndp));
}
int ans=0;
for(int x=0;x<=l;x++){
ans=add(ans,mult(mult(fact[n+l-x],mult(inv_fact[n],inv_fact[l-x])),dp[1][x][2]));
}
cout << ans << endl;
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int t=1;//cin >> t;
while(t--) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
813 ms |
71620 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
34 ms |
20828 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
1116 KB |
Output is correct |
2 |
Correct |
2 ms |
820 KB |
Output is correct |
3 |
Correct |
7 ms |
1116 KB |
Output is correct |
4 |
Correct |
3 ms |
860 KB |
Output is correct |
5 |
Correct |
6 ms |
1116 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
6 ms |
1068 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
856 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
813 ms |
71620 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |