제출 #1150644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150644		AtabayRajabli	Anagramistica (COCI21_anagramistica)	C++20	110 / 110	4 ms	328 KiB

anagramistica

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define int long long
using namespace std;

const int sz = 2e3 + 2, mod = 1e9 + 7;
int n, k, f[sz], inv[sz];
string s;
vector<int> cur, prv;
map<string, int> mp;

int bp(int a, int b, int r = 1)
{
    while(b > 0)
    {
        if(b & 1) r = r * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return r;
}

int C(int n, int k)
{
    if(n < k) return 0;
    return f[n] * inv[k] % mod * inv[n - k] % mod;
}

void solve()
{
    cin >> n >> k;
    prv.resize(k + 1, 0);
    cur.resize(k + 1, 0);
    for(int i = 1; i <= n; i++)
    {
        cin >> s;
        sort(all(s));
        mp[s]++;
    }
    prv[0] = 1;
    for(auto p : mp)
    {
        int freq = p.second;
        for(int i = 0; i * (i - 1) <= freq * (freq - 1); i++)
        {
            int pairs = i * (i - 1) / 2;
            for(int j = pairs; j <= k; j++)
            {
                cur[j] += prv[j - pairs] * C(freq, i) % mod;
                cur[j] %= mod;
            }
        }
        prv = cur;
        fill(all(cur), 0);
    }
    cout << prv[k];
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); 

    inv[0] = f[0] = 1;
    for(int i = 1; i < sz; i++)
    {
        f[i] = f[i - 1] * i % mod;
        inv[i] = bp(f[i], mod - 2);
    }
    
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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