oj.uz

Submission #386345

# Submission time Handle Problem Language Result Execution time Memory
386345 2021-04-06T12:23:38 Z model_code Anagramistica (COCI21_anagramistica) C++17
110 / 110
 145 ms 16364 KB 
#include <iostream>
#include <string>
#include <map>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXM = 2003;
const int MAXK = 2003;
const int MOD = 1000000007;

int ADD(ll a, ll b){
    return (a+b)%MOD;
}
int MUL(ll a, ll b){
    return a*b%MOD;
}
int EXP(ll b, ll e){
    if(e==0) return 1;
    else if(e%2==1) return MUL(b, EXP(b, e-1));
    else return EXP(MUL(b, b), e/2);
}
int DIV(ll a, ll b){
    return MUL(a, EXP(b, MOD-2));
}
int fact[MAXM];
int FACT(ll n){
    return fact[n];
}
int CHOOSE(ll n, ll k){
    return DIV(FACT(n), MUL(FACT(k), FACT(n-k)));
}
int n,k,m;
map<string, int> anagrami;
int a[MAXM];

int dp[MAXM][MAXK];
int solve(int m, int k){
    int& res = dp[m][k];
    if(res == -1){
        if(m == 0){
            if(k == 0) res = 1;
            else res = 0;
        }else{
            res = 0;
            for(int i=0;i <= a[m-1] && k >= i*(i-1)/2;i++){
                res = ADD(res, MUL(CHOOSE(a[m-1], i), solve(m-1, k-i*(i-1)/2)));
            }
        }
    }
    return res;
}

int main(){
    fact[0] = 1;
    for(int i=1;i<MAXM;i++) fact[i] = MUL(i, fact[i-1]);
    for(int i=0;i<MAXM;i++) fill(dp[i], dp[i]+MAXK, -1);
    cin >> n >> k;
    for(int i=0;i<n;i++){
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        anagrami[s]++;
    }
    m = 0;
    for(auto i:anagrami){
        a[m++] = i.second;
    }
    cout << solve(m, k) << endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15980 KB Output is correct
2 Correct 12 ms 16108 KB Output is correct
3 Correct 12 ms 15980 KB Output is correct
4 Correct 14 ms 16108 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15980 KB Output is correct
2 Correct 11 ms 15980 KB Output is correct
3 Correct 11 ms 15980 KB Output is correct
4 Correct 11 ms 15980 KB Output is correct
5 Correct 11 ms 15980 KB Output is correct
6 Correct 12 ms 15980 KB Output is correct
7 Correct 12 ms 16108 KB Output is correct
8 Correct 12 ms 15980 KB Output is correct
9 Correct 14 ms 16108 KB Output is correct
10 Correct 43 ms 16236 KB Output is correct
11 Correct 25 ms 15980 KB Output is correct
12 Correct 13 ms 15980 KB Output is correct
13 Correct 22 ms 15980 KB Output is correct
14 Correct 31 ms 16108 KB Output is correct
15 Correct 20 ms 15980 KB Output is correct
16 Correct 123 ms 16364 KB Output is correct
17 Correct 145 ms 16128 KB Output is correct
18 Correct 13 ms 16108 KB Output is correct