oj.uz

Submission #716263

# Submission time Handle Problem Language Result Execution time Memory
716263 2023-03-29T12:10:50 Z nima_aryan Anagramistica (COCI21_anagramistica) C++17
110 / 110
 12 ms 3328 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   const i64 mod = 1e9 + 7;
   auto binpow = [&](i64 a, i64 b) -> i64 {
      a %= mod;
      i64 ret = 1;
      while (b > 0) {
         if (b & 1) {
            ret *= a;
            ret %= mod;
         }
         a *= a;
         a %= mod;
         b >>= 1;
      }
      return ret;
   };
   const int maxn = (int) 1e5;
   vector<i64> fact(maxn + 1), inv(maxn + 1);
   auto factorial = [&] {
      fact[0] = 1;
      for (int i = 1; i <= maxn; ++i) {
         fact[i] = fact[i - 1] * i % mod;
      }
   };
   factorial();
   auto inversion = [&] {
      inv[maxn] = binpow(fact[maxn], mod - 2);
      for (int i = maxn - 1; i >= 0; --i) {
         inv[i] = inv[i + 1] * (i + 1) % mod;
      }
   };
   inversion();
   auto choose = [&](i64 n, i64 r) -> i64 {
      if (r > n) {
         return 0LL;
      } 
      return fact[n] * inv[r] % mod * inv[n - r] % mod;
   };
   int n, k;
   cin >> n >> k;
   map<string, int> cnt;
   for (int i = 0; i < n; ++i) {
      string s;
      cin >> s;
      sort(s.begin(), s.end());
      cnt[s] += 1;
   }
   const int t = (int) cnt.size();
   vector dp(t + 1, vector<i64>(k + 1));
   dp[0][0] = 1LL;
   int i = 1;
   for (auto [s, c] : cnt) {
      for (int j = 0; j <= k; ++j) {
         for (int x = 0; x <= c; ++x) {
            if (j < choose(x, 2)) {
               continue;
            }
            dp[i][j] += choose(c, x) * dp[i - 1][j - choose(x, 2)] % mod;
            dp[i][j] %= mod;
         }
      }
      ++i;
   }
   cout << dp[t][k] << '\n';
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 3 ms 1876 KB Output is correct
5 Correct 3 ms 1896 KB Output is correct
6 Correct 3 ms 1876 KB Output is correct
7 Correct 3 ms 1876 KB Output is correct
8 Correct 3 ms 1876 KB Output is correct
9 Correct 3 ms 1876 KB Output is correct
10 Correct 4 ms 2388 KB Output is correct
11 Correct 3 ms 1912 KB Output is correct
12 Correct 4 ms 1876 KB Output is correct
13 Correct 4 ms 1912 KB Output is correct
14 Correct 4 ms 2004 KB Output is correct
15 Correct 3 ms 1876 KB Output is correct
16 Correct 8 ms 3328 KB Output is correct
17 Correct 12 ms 2004 KB Output is correct
18 Correct 4 ms 1876 KB Output is correct