Submission #949138

#	Time	Username	Problem	Language	Result	Execution time	Memory
949138		shezitt	Anagramistica (COCI21_anagramistica)	C++14	110 / 110	7 ms	1996 KiB

anagramistica

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define sz(x) (int)x.size()
#define dbg(x) cerr << #x << ": " << x << endl;

using ll = long long;

#define int ll

const int MOD = 1e9+7;  
const int N = 2005;

int bpow(int a, int b){
    int r = 1;
    while(b){
        if(b&1){
            r = r * a % MOD;
        }
        a = a * a % MOD;
        b /= 2;
    }
    return r;
}

int inv(int x){
    return bpow(x, MOD-2);
}

int fact[N];
int invfact[N];

void init(){
    fact[0] = 1;
    invfact[0] = inv(fact[0]);
    for(int i=1; i<N; ++i){
        fact[i] = fact[i-1] * i % MOD;
        invfact[i] = inv(fact[i]);
    }
}

int nck(int n, int k){
    if(k > n) return 0;
    int res = fact[n] * invfact[n-k] % MOD * invfact[k] % MOD;
    return res;
}

signed main(){


    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    init();
    
    int n, k;
    cin >> n >> k;

    vector<string> s(n);

    vector<int> comp;

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

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

    int cur = 1;
    for(int i=1; i<n; ++i){
        if(s[i] != s[i-1]){
            // new
            comp.push_back(cur);
            cur = 1;
        } else {
            cur++;
        }
    }
    comp.push_back(cur);

    int m = sz(comp);
    vector<vector<int>> dp(m+1, vector<int>(k+1, 0));

    dp[0][0] = 1;

    for(int i=0; i<m; ++i){
        for(int j=0; j<=k; ++j){

            for(int tam=0; tam <= comp[i]; ++tam){
                int tmp = nck(tam, 2);
                if(j + tmp > k) break;

                int &res = dp[i+1][j + tmp];

                res = (res + (dp[i][j] * nck(comp[i], tam) % MOD)) % MOD;

            }

        }
    }

    cout << dp[m][k];

}

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