oj.uz

Submission #680006

# Submission time Handle Problem Language Result Execution time Memory
680006 2023-01-09T18:55:05 Z Shadii_usf Anagramistica (COCI21_anagramistica) C++14
40 / 110
 6 ms 2004 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10, mod = 1e9 + 7;
long long  dp[maxn][maxn] , f[maxn] , invf[maxn]  , anss;
long long power(int a , int b){
    if(b == 0){
        return 1;
    }
    anss = power(a , b/2);
    anss *= anss;
    anss %= mod;
    if(b & 1){
        anss *= a;
        anss %= mod;
    }
    return anss;
}
long long c(int n , int k){
    if(k > n){
        return 0;
    }
    return f[n] * invf[k] % mod * invf[n - k] % mod;
}
int main(){
    int n , k , cnt = 1 , sizee;
    string a[maxn];
    bool mark[maxn] , markk[maxn];
    vector <int> v;
    cin >> n >> k;
    for(int i=1 ; i<=n ; i++){
        cin >> a[i];
    }
    for(int i=1 ; i<=n ; i++){
        sizee = a[i].size();
        for(int j = 0 ; j<sizee ; j++){
            mark[a[i][j] - 'a'] = true;
        }
        if(!markk[i]){
            for(int j = 1 ; j<=n ; j++){
                bool x = true;
                if(!markk[j] && j != i){
                    int sizeee = a[j].size();
                    for(int m = 0 ; m<sizee ; m++){
                        if(!mark[a[j][m] - 'a'] || sizeee != sizee){
                            x = false;
                            break;
                        }
                    }
                    if(x){
                        cnt++;
                        markk[j] = true;
                    }
                }
            }
            v.push_back(cnt);
            markk[i] = true;
        }
        sizee = a[i].size();
        for(int j = 0 ; j<sizee ; j++){
            mark[a[i][j] - 'a'] = false;
        }
        cnt = 1;
    }
    f[0] = invf[0] = 1;
    for(int i=1 ; i<maxn ; i++){
        f[i] = f[i-1] * i;
        f[i] %= mod;
        invf[i] = power(f[i] , mod - 2);
    }
    sizee = v.size();
    dp[0][0] = 1;
    for(int i=1 ; i<=sizee ; i++){
        for(int j=0 ; j<=k ; j++){
            for(int m = 0 ; m <= v[i - 1] ; m++){
                if(c(m , 2) <= j){
                    dp[i][j] = dp[i][j] + (dp[i - 1][j - c(m , 2)] * c(v[i-1] , m) % mod) % mod;
                    dp[i][j] %= mod;
                }
            }
        }
    }
    sizee = v.size();
    cout << dp[sizee][k];
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 5 ms 1620 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 6 ms 1660 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 5 ms 1620 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 6 ms 1660 KB Output is correct
10 Incorrect 5 ms 2004 KB Output isn't correct
11 Halted 0 ms 0 KB -