제출 #716263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
716263		nima_aryan	Anagramistica (COCI21_anagramistica)	C++17	110 / 110	12 ms	3328 KiB

anagramistica

#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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70