oj.uz

Submission #516382

# Submission time Handle Problem Language Result Execution time Memory
516382 2022-01-21T09:00:46 Z KoD Anagramistica (COCI21_anagramistica) C++17
110 / 110
 13 ms 332 KB 
#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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 8 ms 332 KB Output is correct
17 Correct 13 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct