Submission #519882

#TimeUsernameProblemLanguageResultExecution timeMemory
519882ViantiAnagramistica (COCI21_anagramistica)C++17
110 / 110
6 ms1812 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; const ll mod = 1e9 + 7; ll fact[10000]; void precalc() { fact[0] = 0; fact[1] = 1; for (int i = 2; i < 10000; i++) { fact[i] = i * fact[i - 1]; fact[i] %= mod; } } ll binpow(ll x, int p) { if (p == 0)return 1; if (p % 2 == 0) { ll res = binpow(x, p / 2); res *= res; res %= mod; return res; } else { return (x * binpow(x, p - 1)) % mod; } } ll inv(ll x) { return binpow(x, mod - 2); } ll C(ll a, ll b) { if (a == b)return 1; if (b == 0)return 1; ll res = fact[a]; ll d = fact[b] * fact[a - b]; d %= mod; res *= inv(d); res %= mod; return res; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); precalc(); int n, k; cin >> n >> k; map<string, int> mp; for (int i = 0; i < n; i++) { string s; cin >> s; sort(s.begin(), s.end()); mp[s]++; } vector<int> a; for (auto& el: mp) { a.push_back(el.second); } n = a.size(); vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, 0)); dp[0][0] = 1; for (int i = 1; i <= n; i++) { vector<ll> b(a[i - 1] + 1, 0); for (int t = 0; t <= a[i - 1]; t++) { b[t] = C(a[i - 1], t); b[t] %= mod; } for (int j = 0; j <= k; j++) { for (int t = 0; t <= a[i - 1]; t++) { int cntpairs = t * (t - 1) / 2; if (cntpairs > j)continue; dp[i][j] += b[t] * dp[i - 1][j - cntpairs]; dp[i][j] %= mod; } } } cout << dp[n][k] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...