Submission #476499

#	Time	Username	Problem	Language	Result	Execution time	Memory
476499		neki	Anagramistica (COCI21_anagramistica)	C++14	110 / 110	91 ms	8552 KiB

anagramistica

#include <bits/stdc++.h>
#define ll long long
#define loop(i, a, b) for(ll i=a;i<b;++i)
#define pool(i, a, b) for(ll i=a-1;i>=b;--i)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 2010
#define par pair<ll, ll>
#define ld long double
#define mod 1000000007
const ll max_num=500100;
ll fac[max_num], inv[max_num];
 
ll pot(ll bas, ll ex){
    ll ret=1;
    for(;ex;ex>>=1, bas=(bas * bas)%mod) if(ex&1)ret=(ret * bas)%mod;
    return ret;
}
 
ll choose(ll a, ll b){
    if(a<b) return 0;
    else return ((fac[a] * inv[a-b])%mod * inv[b])%mod;
}
void calcfac(){
    fac[0]=1;
    loop(i, 1, max_num) fac[i]=(fac[i-1] * i)%mod;
    loop(i, 0, max_num) inv[i]=pot(fac[i], mod-2);
}
 
 
int main() {
    calcfac();
    
    ll n, k;cin >> n >> k;
    map<vc<ll>, ll> cnts;
    loop(i, 0, n){
        string s;cin >> s;
        vc<ll> cnt(26, 0);
        fore(v, s) cnt[v-'a']++;
        cnts[cnt]++;
    }
    
    vc<ll> a;fore(v, cnts) a.ps(v.se);
    
    ll m=a.size();
    
    //cout << choose(2, 2)<<endl;
    
    vc<ll> dp(k+1, 0);dp[0]=1;
    loop(i, 0, m){
        pool(j, k+1, 0) loop(c, 1, a[i]+1) if(j-choose(c, 2)>=0) dp[j]+=dp[j-choose(c, 2)] * choose(a[i], c), dp[j]%=mod;
    }
    cout << dp[k]<<endl;
}

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