oj.uz

Submission #482780

# Submission time Handle Problem Language Result Execution time Memory
482780 2021-10-26T10:21:51 Z radal Anagramistica (COCI21_anagramistica) C++14
110 / 110
 44 ms 14472 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const long long int N = 2e3+20,mod = 1e9+7,inf = 1e9,sq = 65;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,ll k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
int c[N][N],par[N],siz[N],sz[N];
int cnt[N][30],dp[N][2];
int getpar(int v){
    if (par[v] == v) return v;
    return par[v] = getpar(par[v]);
}
void mg(int u,int v){
    u = getpar(u);
    v = getpar(v);
    if (u == v) return;
    par[u] = v;
    sz[v] += sz[u];
    sz[u] = 0;
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,y;
    cin >> n >> y;
    rep(i,0,n+1){
        c[0][i] = 1;
        par[i] = i;
        sz[i] = 1;
    }
    rep(i,1,n+1) rep(j,i,n+1) c[i][j] = mkay(c[i-1][j-1],c[i][j-1]);
    rep(i,1,n+1){
        string s;
        cin >> s;
        siz[i] = s.size();
        rep(j,0,siz[i]) cnt[i][s[j]-'a']++;
        rep(j,1,i){
            if (siz[j] != siz[i] || getpar(i) == getpar(j)) continue;
            bool f = 1;
            rep(k,0,26){
                if (cnt[i][k] != cnt[j][k]){
                    f = 0;
                    break;
                }
            }
            if (f) mg(i,j);
        }
    }
    vector<int> ve;
    ve.reserve(2001);
    rep(i,1,n+1) if (sz[i]) ve.pb(sz[i]);
    bool f = 1;
    dp[0][0] = 1;
    for (int u : ve){
        rep(i,0,y+1){
            dp[i][f] = 0;
            rep(j,0,u+1){
                if (c[2][j] > i) break;
                dp[i][f] = mkay(dp[i][f],1ll*dp[i-c[2][j]][!f]*c[j][u]%mod);
            }
        }
        f = !f;
    }
    cout << dp[y][!f];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 0 ms 324 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 14 ms 8388 KB Output is correct
2 Correct 22 ms 10452 KB Output is correct
3 Correct 23 ms 12396 KB Output is correct
4 Correct 30 ms 14472 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 0 ms 324 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 14 ms 8388 KB Output is correct
7 Correct 22 ms 10452 KB Output is correct
8 Correct 23 ms 12396 KB Output is correct
9 Correct 30 ms 14472 KB Output is correct
10 Correct 5 ms 3532 KB Output is correct
11 Correct 5 ms 3504 KB Output is correct
12 Correct 10 ms 6476 KB Output is correct
13 Correct 10 ms 6476 KB Output is correct
14 Correct 25 ms 10480 KB Output is correct
15 Correct 19 ms 10484 KB Output is correct
16 Correct 36 ms 14420 KB Output is correct
17 Correct 36 ms 14408 KB Output is correct
18 Correct 44 ms 14372 KB Output is correct