Submission #1302976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302976		duckindog	Anagramistica (COCI21_anagramistica)	C++20	110 / 110	7 ms	5696 KiB

anagramistica

#include <bits/stdc++.h>

using namespace std;

const int N = 2000 + 10,
            M = 1'000'000'007;
int n, k;
string s[N];

inline void add(auto& x, const auto& y) {
    x += y;
    if (x >= M) x -= M;
}
inline int powder(int a, int b) {
    int ret = 1;
    for (; b; b /= 2, a = 1ll * a * a % M) {
        if (b & 1) ret = 1ll * ret * a % M;
    }
    return ret;
}

int fac[N], ifac[N];
inline int C(int n, int k) { return 1ll * fac[n] * ifac[n - k] % M * ifac[k] % M; }

int f[N][N];

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    if (fopen("input.txt", "r")) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
    if (fopen("anagramistica.inp", "r")) {
        freopen("anagramistica.inp", "r", stdin);
        freopen("anagramistica.out", "w", stdout);
    }

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> s[i];

    for (int i = 1; i <= n; ++i) {
        sort(s[i].begin(), s[i].end());
    }
    sort(s + 1, s + n + 1);

    vector<int> vt;
    { // cal vt
        string last;
        for (int i = 1; i <= n; ++i) {
            if (s[i] != last) last = s[i], vt.push_back(0);
            vt.back() += 1;
        }
    }

    { // init fact
        fac[0] = 1;
        for (int i = 1; i < N; ++i) fac[i] = 1ll * fac[i - 1] * i % M;
        ifac[N - 1] = powder(fac[N - 1], M - 2);
        for (int i = N - 1; i >= 1; --i) ifac[i - 1] = 1ll * ifac[i] * i % M;
    }

    vt.insert(vt.begin(), 0);

    f[0][0] = 1;
    for (int i = 1; i < (int)vt.size(); ++i) {
        for (int j = 0; j <= k; ++j) {
            auto& ret = f[i][j];
            for (int choose = 0; choose <= vt[i]; ++choose) {
                int pii = choose * (choose - 1) / 2;
                if (pii > j) break;
                add(ret, 1ll * f[i - 1][j - pii] * C(vt[i], choose) % M);
            }
        }
    }

    cout << f[vt.size() - 1][k] << "\n";
}

Compilation message (stderr)

anagramistica.cpp: In function 'int32_t main()':
anagramistica.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
anagramistica.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
anagramistica.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen("anagramistica.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
anagramistica.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen("anagramistica.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70