#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); 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
anagramistica.cpp:2:9: warning: #pragma once in main file
2 | #pragma once
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2396 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2396 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
2396 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
