Submission #386874

#TimeUsernameProblemLanguageResultExecution timeMemory
386874phathnvAnagramistica (COCI21_anagramistica)C++11
110 / 110
19 ms19436 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2007; const int MOD = 1e9 + 7; int n, k, numWord, c[N]; int nCk[N][N], dp[N][N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; map<string, int> cnt; for(int i = 1; i <= n; i++){ string s; cin >> s; sort(s.begin(), s.end()); cnt[s]++; } for(auto p : cnt) c[++numWord] = p.second; for(int i = 0; i <= n; i++){ nCk[i][0] = 1; for(int j = 1; j <= i; j++) nCk[i][j] = (nCk[i - 1][j] + nCk[i - 1][j - 1]) % MOD; } dp[0][0] = 1; for(int i = 0; i < numWord; i++) for(int j = 0; j <= k; j++) for(int x = 0; x <= c[i + 1]; x++){ int nxtJ = j + x * (x - 1) / 2; if (nxtJ <= k) dp[i + 1][nxtJ] = (dp[i + 1][nxtJ] + (ll) dp[i][j] * nCk[c[i + 1]][x] % MOD) % MOD; } cout << dp[numWord][k]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...