oj.uz

Submission #404022

# Submission time Handle Problem Language Result Execution time Memory
404022 2021-05-13T17:03:20 Z ScarletS Anagramistica (COCI21_anagramistica) C++17
110 / 110
 98 ms 6516 KB 
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

const int mn = 2001, mod = 1e9+7;
int a[mn];
ll ft[mn],dp[mn][mn];
map<vector<int>,int> m;

ll binpow(ll a, ll b)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = (res * a)%mod;
        a = (a * a)%mod;
        b >>= 1;
    }
    return res;
}

ll mult(ll a, ll b)
{
    return (a*b)%mod;
}

ll C(int n, int k)
{
    return mult(ft[n],binpow(mult(ft[k],ft[n-k]),mod-2));
}

ll calc(ll n)
{
    return mult(mult(n,n-1),(mod+1)/2);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,K,x=0;
    cin>>n>>K;
    string s;
    dp[0][0]=1;
    ft[0]=1;
    for (int i=0;i<n;++i)
    {
        ft[i+1]=(ft[i]*(i+1))%mod;
        vector<int> f(26,0);
        cin>>s;
        for (auto j : s)
            ++f[j-'a'];
        if (!m[f])
            m[f]=++x;
        ++a[m[f]];
    }
    for (int i=1;i<=x;++i)
        for (int j=0;j<=K;++j)
            for (int k=0;k<=a[i]&&calc(k)<=j;++k)
                dp[i][j]=(dp[i][j]+mult(dp[i-1][j-calc(k)],C(a[i],k)))%mod;
    cout<<dp[x][K];
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 3 ms 1612 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 4 ms 1612 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 3 ms 1612 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 4 ms 1612 KB Output is correct
10 Correct 31 ms 2000 KB Output is correct
11 Correct 9 ms 460 KB Output is correct
12 Correct 2 ms 552 KB Output is correct
13 Correct 10 ms 456 KB Output is correct
14 Correct 16 ms 1228 KB Output is correct
15 Correct 7 ms 460 KB Output is correct
16 Correct 89 ms 6516 KB Output is correct
17 Correct 98 ms 608 KB Output is correct
18 Correct 3 ms 1352 KB Output is correct