oj.uz

Submission #476499

# Submission time Handle Problem Language Result Execution time Memory
476499 2021-09-27T11:51:48 Z neki Anagramistica (COCI21_anagramistica) C++14
110 / 110
 91 ms 8552 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), dp[j]%=mod;
    }
    cout << dp[k]<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 8064 KB Output is correct
2 Correct 80 ms 8104 KB Output is correct
3 Correct 81 ms 8004 KB Output is correct
4 Correct 81 ms 8104 KB Output is correct
5 Correct 80 ms 8004 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 8072 KB Output is correct
2 Correct 82 ms 8156 KB Output is correct
3 Correct 82 ms 8132 KB Output is correct
4 Correct 82 ms 8212 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 8064 KB Output is correct
2 Correct 80 ms 8104 KB Output is correct
3 Correct 81 ms 8004 KB Output is correct
4 Correct 81 ms 8104 KB Output is correct
5 Correct 80 ms 8004 KB Output is correct
6 Correct 81 ms 8072 KB Output is correct
7 Correct 82 ms 8156 KB Output is correct
8 Correct 82 ms 8132 KB Output is correct
9 Correct 82 ms 8212 KB Output is correct
10 Correct 82 ms 8096 KB Output is correct
11 Correct 81 ms 8004 KB Output is correct
12 Correct 81 ms 8016 KB Output is correct
13 Correct 82 ms 8064 KB Output is correct
14 Correct 86 ms 8180 KB Output is correct
15 Correct 83 ms 8036 KB Output is correct
16 Correct 87 ms 8552 KB Output is correct
17 Correct 91 ms 8116 KB Output is correct
18 Correct 82 ms 8160 KB Output is correct