Submission #680020

#	Time	Username	Problem	Language	Result	Execution time	Memory
680020		Shadii_usf	Anagramistica (COCI21_anagramistica)	C++14	110 / 110	29 ms	32040 KiB

anagramistica

#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(){
    long long n , k , cnt = 0 , 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];
        sort(a[i].begin() , a[i].end());
    }
    for(int i=0 ; i<maxn ; i++){
        mark[i] = 0;
        for(int j=0 ; j<maxn ; j++){
            dp[i][j] = 0;
        }
    }
    for(int i=1 ; i<=n ; i++){
        if(!mark[i]){
            for(int j = 1 ; j<=n ; j++){
                if(a[i] == a[j] && !mark[j]){
                    mark[j] = true;
                    cnt++;
                }
            }
            v.push_back(cnt);
            cnt = 0;
        }
    }
    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];
}

Compilation message (stderr)

anagramistica.cpp: In function 'int main()':
anagramistica.cpp:27:23: warning: unused variable 'markk' [-Wunused-variable]
   27 |     bool mark[maxn] , markk[maxn];
      |                       ^~~~~

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