This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
* In the name of God
*
* Author: Farbod Doost
* Last Modified: Mon, 27 Mar 2023 (14:38:55)
*
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const long long mod = 1e9 + 7;
long long fact[N], inv[N];
int n, k, cnt[N], T = 0;
map <string, int> mp;
long long dp[N][N];
long long p(long long n, long long r)
{
if (r == 0)
return 1;
if (r == 1)
return n;
long long c = p(n, r / 2);
return c * c % mod * p(n, r % 2) % mod;
}
long long C(int n, int r)
{
return fact[n] * inv[r] % mod * inv[n - r] % mod;
}
signed main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
fact[0] = inv[0] = 1;
for (int i = 1; i < N; i++)
fact[i] = fact[i - 1] * i % mod,
inv[i] = p(fact[i], mod - 2);
cin >> n >> k;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
sort(s.begin(), s.end());
if (mp[s] == 0)
mp[s] = ++T;
cnt[mp[s]]++;
}
dp[0][0] = 1;
for (int j = 0; j <= k; j++)
for (int i = 1; i <= T; i++)
for (int l = 0; l * (l - 1) / 2 <= j && l <= cnt[i]; l++)
dp[i][j] += (dp[i - 1][j - l * (l - 1) / 2] * C(cnt[i], l) % mod),
dp[i][j] %= mod;
cout << dp[T][k];
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |