oj.uz

Submission #855905

# Submission time Handle Problem Language Result Execution time Memory
855905 2023-10-02T08:51:48 Z wakandaaa Anagramistica (COCI21_anagramistica) C++17
110 / 110
 19 ms 22360 KB 
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return l + rd() % (r - l + 1);
}

const int N = 2e3 + 5;
const int mod = 1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int inf = 1e9; // INT_MAX;
const long long llinf = 1e18; // LLONG_MAX;

template<class X, class Y>
bool minimize(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}

template<class X, class Y>
bool maximize(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}

template<class X, class Y>
bool add(X &a, Y b) {
    a += b;
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return true;
}

int n, k;
unordered_map<string, int> rec;
int c[N][N];
int f[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        sort(all(s));
        rec[s]++;
    }

    for (int i = 1; i <= n; ++i) {
        c[0][i] = c[i][i] = 1;
        for (int j = 1; j < i; ++j) {
            add(c[j][i], c[j - 1][i - 1]);
            add(c[j][i], c[j][i - 1]);
        }
    }

    vector<int> words;
    for (auto [s, i] : rec) words.push_back(i);
    f[0][0] = 1;

    for (int i = 1; i <= (int) words.size(); ++i) {
        for (int cnt = 0; cnt <= words[i - 1]; ++cnt) {
            for (int j = 0; j <= k; ++j) {
                int offset = max(0, cnt * (cnt - 1) / 2);
                if (j - offset >= 0) {
                    add(f[i][j], 1LL * c[cnt][words[i - 1]] * f[i - 1][j - offset] % mod);
                }
            }
        }
    }

    cout << f[(int) words.size()][k];

    return 0;
}

/*

*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2512 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12944 KB Output is correct
2 Correct 7 ms 15960 KB Output is correct
3 Correct 9 ms 16988 KB Output is correct
4 Correct 13 ms 18200 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2512 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 5 ms 12944 KB Output is correct
7 Correct 7 ms 15960 KB Output is correct
8 Correct 9 ms 16988 KB Output is correct
9 Correct 13 ms 18200 KB Output is correct
10 Correct 4 ms 8024 KB Output is correct
11 Correct 2 ms 6620 KB Output is correct
12 Correct 4 ms 10972 KB Output is correct
13 Correct 4 ms 10744 KB Output is correct
14 Correct 8 ms 15708 KB Output is correct
15 Correct 8 ms 14940 KB Output is correct
16 Correct 17 ms 22360 KB Output is correct
17 Correct 19 ms 17244 KB Output is correct
18 Correct 12 ms 18012 KB Output is correct