Submission #715704

#TimeUsernameProblemLanguageResultExecution timeMemory
715704hamidh100Anagramistica (COCI21_anagramistica)C++17
110 / 110
19 ms5648 KiB
/* In the name of God */ #include <iostream> #include <iomanip> #include <stdlib.h> #include <stdio.h> #include <math.h> #include <string> #include <string.h> #include <algorithm> #include <bitset> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <map> #include <numeric> #include <limits> #include <limits.h> #include <unordered_map> #include <unordered_set> #include <chrono> #include <random> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; typedef map<int, int> MPII; typedef vector<int> VI; typedef vector<ll> VL; #define PB push_back #define POP pop_back #define MP make_pair #define all(a) (a).begin(), (a).end() #define endl '\n' #define dbg(x) cerr << '[' << #x << ": " << x << "]\n" #define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n" #define Yes cout << "Yes\n" #define YES cout << "YES\n" #define No cout << "No\n" #define NO cout << "NO\n" const ll INF = (ll)2e18 + 1386; const ld eps = 0.000000000000001; int MOD = 1e9 + 7; inline int mod_(int a){ int res = a + MOD; return (res >= MOD? res - MOD : res); } inline int mod_add(int a, int b){ int res = a + b; return (res >= MOD? res - MOD : res); } inline int mod_neg(int a, int b){ int res = (abs(a - b) < MOD? a - b : (a - b) % MOD); return (res < 0? res + MOD : res); } inline int mod_mlt(int a, int b){ return (1ll * a * b % MOD); } inline string intToString(ll a){ char x[100]; sprintf(x, "%lld", a); string s = x; return s; } inline ll stringToInt(string s){ ll res; char x[100]; strcpy(x, s.c_str()); sscanf(x, "%lld", &res); return res; } inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); } const int MAXN = 2001; int dp[MAXN][MAXN], mods[] = {923232361, (int)1e9 + 9, 1000696969}, base = 9239; ll fact[MAXN], inv[MAXN]; map<pair<int, PII>, int> cnt; vector<pair<int, PII>> vec; ll poww(ll x, int y, int p = MOD){ ll res = 1; x %= p; while (y > 0){ if (y & 1) res = (res * x) % p; y >>= 1; x = (x * x) % p; } return res; } void initFact(int _limit = MAXN){ fact[0] = 1; for (int i = 1; i < _limit; i++){ fact[i] = mod_mlt(fact[i - 1], i); } } void initInv(int _limit = MAXN){ inv[_limit - 1] = poww(fact[_limit - 1], MOD - 2); for (int i = _limit - 2; i >= 0; i--){ inv[i] = mod_mlt(inv[i + 1], i + 1); } } ll nCr(int n, int r){ if (n < r) return 0; if (r == 0 || n == r) return 1; return (fact[n] * inv[r] % MOD * inv[n - r] % MOD) % MOD; } pair<int, PII> Hash(string s){ int res[] = {0, 0, 0}; for (int i = 0; i < 3; i++){ MOD = mods[i]; for (char ch : s){ res[i] = mod_add(mod_mlt(res[i], base), ch - 'a' + 1); } } return MP(res[0], MP(res[1], res[2])); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); initFact(), initInv(); int n, k; cin >> n >> k; while (n--){ string s; cin >> s; sort(all(s)); auto x = Hash(s); vec.PB(x); cnt[x]++; } vec.PB(MP(0, MP(0, 0))); sort(all(vec)); vec.resize(unique(vec.begin(), vec.end()) - vec.begin()); n = vec.size(); dp[0][0] = 1; MOD = (int)1e9 + 7; for (int i = 1; i < n; i++){ auto H = vec[i]; int c = cnt[H]; for (int j = 0; j <= k; j++){ dp[i][j] = mod_mlt(dp[i - 1][j], c + 1); for (int k = 2; k <= c; k++){ if (1ll * k * (k - 1) / 2 > j) break; dp[i][j] = mod_add(dp[i][j], mod_mlt(nCr(c, k), dp[i - 1][j - (k * (k - 1) / 2)])); } } } cout << dp[n - 1][k]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...