Submission #397611

#TimeUsernameProblemLanguageResultExecution timeMemory
397611MrRobot_28Anagramistica (COCI21_anagramistica)C++17
110 / 110
31 ms35140 KiB
#include<bits/stdc++.h> using namespace std; #define X first #define Y second #define int long long #define sz(a) (int)a.size() const int mod = 1e9 + 7; const int N = 2e3 + 100; int cnk[N][N]; signed main() { // ifstream cin("input1.txt.4c"); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { cnk[i][j] = 0; } } cnk[0][0] = 1; for(int i = 1; i < N; i++) { cnk[i][0] = 1; for(int j = 1; j < N; j++) { cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % mod; } } int n, k; cin >> n >> k; map<vector <int>, int> mp; for(int i = 0; i < n; i++) { string s; cin >> s; vector <int> cnt(26, 0); for(int j = 0; j < sz(s); j++) { cnt[s[j] - 'a']++; } mp[cnt]++; } vector <int> dp(k + 1, 0); dp[0] = 1; for(auto p : mp) { int t = p.Y; for(int j = k; j >= 0; j--) { for(int f = t; f >= 1; f--) { int add = f * (f - 1) / 2; // cout << dp[j] << " " << add << " " << cnk[t][f] << "\n"; if(add + j <= k) { dp[add + j] = (dp[add + j] + dp[j] * cnk[t][f]) % mod; } } } // cout << dp[k] << "\n"; } cout << dp[k]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...