oj.uz

Submission #873918

# Submission time Handle Problem Language Result Execution time Memory
873918 2023-11-16T02:44:13 Z noiaint Anagramistica (COCI21_anagramistica) C++17
110 / 110
 20 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 2396 KB Output is correct
2 Correct 1 ms 2404 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2512 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12892 KB Output is correct
2 Correct 8 ms 16156 KB Output is correct
3 Correct 9 ms 16988 KB Output is correct
4 Correct 12 ms 18328 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2404 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2512 KB Output is correct
6 Correct 6 ms 12892 KB Output is correct
7 Correct 8 ms 16156 KB Output is correct
8 Correct 9 ms 16988 KB Output is correct
9 Correct 12 ms 18328 KB Output is correct
10 Correct 3 ms 8028 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 4 ms 10844 KB Output is correct
13 Correct 4 ms 10844 KB Output is correct
14 Correct 8 ms 15616 KB Output is correct
15 Correct 8 ms 14940 KB Output is correct
16 Correct 17 ms 22360 KB Output is correct
17 Correct 20 ms 17416 KB Output is correct
18 Correct 12 ms 18012 KB Output is correct