Submission #715636

#TimeUsernameProblemLanguageResultExecution timeMemory
715636FarbodAnagramistica (COCI21_anagramistica)C++17
0 / 110
1 ms504 KiB
/* * In the name of God * * Author: Farbod Doost * Last Modified: Mon, 27 Mar 2023 (13:53:38) * */ #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, int 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]]++; } for (int i = 0; i <= T; i++) dp[i][0] = 1; for (int j = 1; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...