This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
constexpr int MOD = 1000000007;
struct Fp {
int x;
Fp(int x = 0) : x(x) {}
Fp& operator+=(const Fp& t) {
if ((x += t.x) >= MOD) x -= MOD;
return *this;
}
Fp& operator*=(const Fp& t) {
x = (long long)x * t.x % MOD;
return *this;
}
Fp operator+(const Fp& t) const {
return Fp(*this) += t;
}
Fp operator*(const Fp& t) const {
return Fp(*this) *= t;
}
Fp pow(int e) const {
Fp ret(1), mul(*this);
while (e > 0) {
if (e & 1) ret *= mul;
mul *= mul;
e >>= 1;
}
return ret;
}
Fp inv() const {
return pow(MOD - 2);
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, K;
std::cin >> N >> K;
std::map<std::string, int> map;
for (int i = 0; i < N; ++i) {
std::string s;
std::cin >> s;
std::sort(s.begin(), s.end());
map[s] += 1;
}
vector<Fp> fact(N + 1);
fact[0] = 1;
for (int i = 1; i <= N; ++i) {
fact[i] = fact[i - 1] * i;
}
vector<Fp> inv_fact(N + 1);
inv_fact[N] = fact[N].inv();
for (int i = N; i >= 1; --i) {
inv_fact[i - 1] = inv_fact[i] * i;
}
const auto binom = [&](const int n, const int r) {
return fact[n] * inv_fact[r] * inv_fact[n - r];
};
vector<Fp> dp(K + 1);
dp[0] = 1;
for (const auto& [s, n] : map) {
vector<Fp> next(K + 1);
for (int i = 0; i <= K; ++i) {
for (int j = 0; j <= n; ++j) {
const int ni = i + j * (j - 1) / 2;
if (ni <= K) {
next[ni] += dp[i] * binom(n, j);
}
}
}
dp = std::move(next);
}
std::cout << dp[K].x << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |