Submission #1066087

#TimeUsernameProblemLanguageResultExecution timeMemory
1066087coolboy19521Anagramistica (COCI21_anagramistica)C++17
110 / 110
5 ms1420 KiB
#pragma GCC optimize("Ofast") #pragma once #include <bits/stdc++.h> namespace ddr { #define bpc(bt) __builtin_popcountll(bt) #define bcl(bt) __builtin_clz(bt) #define alr(v) rbegin(v),rend(v) #define all(v) begin(v),end(v) #define si(v) ((ll)v.size()) #define lob lower_bound #define upb upper_bound #define pub push_back #define pob pop_back #define mp make_pair #define ins insert #define se second #define fi first template<class T,size_t N> using ar = std::array<T, N>; template<class T,class U> using pi = std::pair<T, U>; template<class T> using pq = std::priority_queue<T>; template<class T> using mt = std::multiset<T>; template<class T> using ve = std::vector<T>; template<class T> using qu = std::queue<T>; typedef std::string str; typedef long double ld; typedef long long ll; using namespace std; const int iinf = INT_MAX; const ll inf = 1e18 + 18; const ll md = 1e9 + 7; const ll mo = 998244353; } using namespace ddr; template<class T> struct STree { vector<T> st; function<T(T,T)> f; T df, n; STree(T _n, T _df, function<T(T,T)> _f) { n = _n; df = _df; f = _f; st.assign(2 * (n + 1), _df); } void set(T v, T k) { st[v += n] = k; for (v /= 2; v; v /= 2) st[v] = f(st[v * 2], st[v * 2 + 1]); } T qry(T lo, T hi) { T r = df; for (lo += n, hi += n + 1; lo < hi; lo /= 2, hi /= 2) { if (lo & 1) r = f(r, st[lo ++]); if (hi & 1) r = f(r, st[-- hi]); } return r; } }; template<class T> struct FTree { vector<T> st; T n; FTree(T _n) { n = _n; st.assign(n + 1, 0); } void add(T v, T k) { for (; v <= n; v += v & -v) st[v] += k; } void set(T v, T k) { int bf = qrt(v, v); for (; v <= n; v += v & -v) st[v] += k - bf; } T qry(T lo, T hi) { lo --; T lq = 0; for (; 0 < lo; lo -= lo & -lo) lq += st[lo]; T rq = 0; for (; 0 < hi; hi -= hi & -hi) rq += st[hi]; return rq - lq; } }; template<class T> struct DSU { vector<T> par; DSU(T n) { par.assign(n + 1, -1); } T Find(T v) { if (0 > par[v]) return v; return par[v] = Find(par[v]); } bool Unite(T u, T v) { u = Find(u); v = Find(v); if (par[u] > par[v]) swap(u, v); if (u == v) return false; par[u] += par[v]; par[v] = u; return true; } }; template<class T> void show(vector<T> v, char bt) { for (T i : v) cout << i << bt; cout << '\n'; } template<class T> void show(T a[], size_t n, char bt) { for (size_t i = 0; i < n; i ++) cout << a[i] << bt; cout << '\n'; } template<class T> void show(T* a, size_t n, size_t m, char bt) { for (size_t i = 0; i < n; i ++) show(a[i], m, bt); } #define int ll const int sz = 2e3 + 6; const int sm = 62; int nw[sz], ol[sz]; int c[sz][sm]; signed main() { int n, k; cin >> n >> k; for (int i = 0; i < sz; i ++) { for (int j = 0; j <= min(i, sm - 1); j ++) { if (0 == j || i == j) c[i][j] = 1; else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % md; } } map<str,int> cn; for (int i = 0; i < n; i ++) { str s; cin >> s; sort(all(s)); cn[s] ++; } ol[0] = 1; for (auto& [_, nm] : cn) { for (int i = 1; i <= nm; i ++) { int cho = i * (i - 1) / 2; for (int j = k; cho <= j; j --) (nw[j] += c[nm][i] * ol[j - cho] % md) %= md; } for (int i = 0; i <= k; i ++) { (ol[i] += nw[i]) %= md; nw[i] = 0; } } cout << ol[k] << '\n'; }

Compilation message (stderr)

anagramistica.cpp:2:9: warning: #pragma once in main file
    2 | #pragma once
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...