This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define PB push_back
#define M ll(1e9 + 7)
#define sz(x) (ll)x.size()
#define N 100005
#define pri(x) cout << x << endl
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define _ << " " <<
using namespace std;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef short int si;
typedef unsigned long long ull;
int mlt(int x, int y)
{
return 1ll * x * y % M;
}
int sm(int x, int y)
{
x += y;
if (x >= M)
x -= M;
return x;
}
int fact[N];
int binpow(int a, int b)
{
if (b == 0)
return 1;
int s = binpow(a, b >> 1);
s = mlt(s, s);
if (b & 1)
s = mlt(s, a);
return s;
}
int C(int n, int k)
{
return mlt(fact[n], binpow(mlt(fact[k], fact[n - k]), M - 2));
}
int ans, n, l;
int dp[55][10500];
int lst[55][10500];
int main()
{
istream::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
fact[0] = 1;
for (int i = 1; i < N; i++)
fact[i] = mlt(fact[i - 1], i);
cin >> n >> l;
vector <int> r(n);
for (int i = 0; i < n; i++)
cin >> r[i];
sort(all(r));
lst[0][0] = 1;
for (int i = 0; i < n; i++)
{
memset(dp, 0, sizeof dp);
for (int j = 1; j <= i + 1; j++)
for (int k = 1; k <= l; k++)
{
dp[j][k] = lst[j - 1][k - 1];
if (k >= r[i])
dp[j][k] = sm(dp[j][k], mlt(j + j, lst[j][k - r[i]]));
if (k + 1 >= r[i] + r[i])
dp[j][k] = sm(dp[j][k], mlt(j * (j + 1), lst[j + 1][k - r[i] - r[i] + 1]));
}
lst[0][0] = 0;
for (int j = 1; j <= i + 1; j++)
for (int k = 1; k <= l; k++)
{
lst[j][k] = dp[j][k];
}
}
for (int u = 1; u <= l; u++)
ans = sm(ans, mlt(C(n + l - u, n), lst[1][u]));
pri(ans);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |