oj.uz

Submission #949138

# Submission time Handle Problem Language Result Execution time Memory
949138 2024-03-19T02:13:05 Z shezitt Anagramistica (COCI21_anagramistica) C++14
110 / 110
 7 ms 1996 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 500 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 500 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 536 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 6 ms 1996 KB Output is correct
17 Correct 7 ms 600 KB Output is correct
18 Correct 1 ms 348 KB Output is correct