제출 #1168621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168621		toast12	Anagramistica (COCI21_anagramistica)	C++20	110 / 110	64 ms	444 KiB

anagramistica

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MOD = 1e9+7;
const int MAXN = 2000;

vector<ll> fact;

ll inv(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b % 2 == 1) {
            res *= a;
            res %= MOD;
        }
        b /= 2;
        a *= a;
        a %= MOD;
    }
    return res;
}

ll nCr(ll n, ll r) {
    if (r == 0) return 1;
    return fact[n]*inv((fact[r]*fact[n-r]) % MOD, MOD-2) % MOD;
}

int main() {
    fact.resize(MAXN+1);
    fact[0] = 1;
    for (int i = 1; i <= MAXN; i++) fact[i] = (fact[i-1]*i) % MOD;
    int n, k;
    cin >> n >> k;
    map<string, int> freq;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        freq[s]++;
    }
    // dp[j] stores the number of subsets possible if there are exactly j similar pairs
    vector<ll> dp(k+1);
    dp[0] = 1;
    for (auto x : freq) {
        int f = x.second;
        for (int j = k; j >= 0; j--) {
            for (int p = 1; p <= f; p++) {
                if (p*(p-1)/2 <= j) {
                    dp[j] += dp[j-(p*(p-1)/2)]*nCr(f, p) % MOD;
                    dp[j] %= MOD;
                }
                else break;
            }
        }
    }
    cout << dp[k] << '\n';
    return 0;
}

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