Submission #386345

#	Time	Username	Problem	Language	Result	Execution time	Memory
386345		model_code	Anagramistica (COCI21_anagramistica)	C++17	110 / 110	145 ms	16364 KiB

anagramistica

#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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70