oj.uz

Submission #1066087

# Submission time Handle Problem Language Result Execution time Memory
1066087 2024-08-19T14:55:15 Z coolboy19521 Anagramistica (COCI21_anagramistica) C++17
110 / 110
 5 ms 1420 KB 
#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

anagramistica.cpp:2:9: warning: #pragma once in main file
    2 | #pragma once
      |         ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
70.0 / 70.0

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