oj.uz

Submission #476498

# Submission time Handle Problem Language Result Execution time Memory
476498 2021-09-27T11:49:53 Z neki Anagramistica (COCI21_anagramistica) C++14
10 / 110
 82 ms 8192 KB 
#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);
    }
    cout << dp[k]<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 8032 KB Output is correct
2 Correct 80 ms 8096 KB Output is correct
3 Correct 81 ms 8192 KB Output is correct
4 Correct 81 ms 8004 KB Output is correct
5 Correct 81 ms 8040 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 8100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 8032 KB Output is correct
2 Correct 80 ms 8096 KB Output is correct
3 Correct 81 ms 8192 KB Output is correct
4 Correct 81 ms 8004 KB Output is correct
5 Correct 81 ms 8040 KB Output is correct
6 Incorrect 82 ms 8100 KB Output isn't correct
7 Halted 0 ms 0 KB -