Submission #494330

#	Time	Username	Problem	Language	Result	Execution time	Memory
494330		AlperenT	Anagramistica (COCI21_anagramistica)	C++17	110 / 110	17 ms	460 KiB

anagramistica

#include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 5, MOD = 1e9 + 7;

struct mint{
    int val;

    mint(long long a = 0) : val(a % MOD) {if(val < 0) val += MOD; }
    mint(long long a, long long b) {*this += a, *this /= b; }

    mint &operator += (const mint &b) {val += b.val; if(val >= MOD) val -= MOD; return *this; }
    mint &operator -= (const mint &b) {val -= b.val; if(val < 0) val += MOD; return *this; }
    mint &operator *= (const mint &b) {val = (1ll * val * b.val) % MOD; return *this; }

    mint mexp(mint a, long long b){
        mint c(1);
        for(; b > 0; b /= 2, a *= a) if(b & 1) c *= a;
        return c;
    }

    mint minv(const mint &a) {return mexp(a, MOD - 2); }

    mint &operator /= (const mint &b) {return *this *= minv(b); }

    friend mint operator + (mint a, const mint &b) {return a += b; }
    friend mint operator - (mint a, const mint &b) {return a -= b; }
    friend mint operator * (mint a, const mint &b) {return a *= b; }
    friend mint operator / (mint a, const mint &b) {return a /= b; }

    friend bool operator == (const mint &a, const mint &b) {return a.val == b.val; }
    friend bool operator != (const mint &a, const mint &b) {return a.val != b.val; }

    friend istream &operator >> (istream &is, mint &a) {long long b; is >> b; a = b; return is; }
    friend ostream &operator << (ostream &os, const mint &a) {return os << a.val; }
};

int n, k, paircnt;

mint fact[N], invfact[N], knap[N], knap2[N];

vector<pair<int, mint>> v;

bool isknap[N], isknap2[N];

map<string, int> mp;
string str;

mint comb(int a, int b){
    return fact[a] * (invfact[b] * invfact[a - b]);
}

void precalc(){
    fact[0] = 1;
    for(int i = 1; i < N; i++) fact[i] = fact[i - 1] * i;

    invfact[N - 1] = mint(0).minv(fact[N - 1]);
    for(int i = N - 2; i >= 0; i--) invfact[i] = invfact[i + 1] * (i + 1);
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    precalc();

    cin >> n >> k;

    for(int i = 0; i < n; i++){
        cin >> str;

        sort(str.begin(), str.end());

        mp[str]++;
    }

    isknap[0] = true;
    knap[0] = 1;

    for(auto p : mp){
        v.clear();

        for(int i = 1; i <= p.second; i++){
            paircnt = (i * (i - 1)) / 2;

            if(paircnt < N) v.push_back({paircnt, comb(p.second, i)});
        }

        fill(knap2, knap2 + N, 0);
        memset(isknap2, 0, sizeof(isknap2));

        for(auto itm : v){
            for(int i = N - 1; i >= itm.first; i--){
                if(isknap[i - itm.first]){
                    isknap2[i] = true;
                    knap2[i] += knap[i - itm.first] * itm.second;
                }
            }
        }

        for(int i = 0; i < N; i++) isknap[i] |= isknap2[i], knap[i] += knap2[i];
    }

    cout << knap[k];
}

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