結果

問題 No.603 hel__world (2)
ユーザー zimphazimpha
提出日時 2017-12-03 02:25:20
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,353 bytes
コンパイル時間 1,046 ms
コンパイル使用メモリ 52,700 KB
実行使用メモリ 24,432 KB
最終ジャッジ日時 2023-08-18 22:17:41
合計ジャッジ時間 7,741 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge9
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 14 ms
18,600 KB
testcase_01 AC 13 ms
18,600 KB
testcase_02 AC 13 ms
18,660 KB
testcase_03 AC 13 ms
18,624 KB
testcase_04 AC 13 ms
18,648 KB
testcase_05 AC 13 ms
18,596 KB
testcase_06 AC 14 ms
18,596 KB
testcase_07 AC 13 ms
18,596 KB
testcase_08 AC 13 ms
18,656 KB
testcase_09 AC 13 ms
18,600 KB
testcase_10 AC 13 ms
18,672 KB
testcase_11 AC 66 ms
24,212 KB
testcase_12 AC 45 ms
24,168 KB
testcase_13 AC 52 ms
24,108 KB
testcase_14 AC 14 ms
18,632 KB
testcase_15 RE -
testcase_16 AC 14 ms
18,600 KB
testcase_17 AC 13 ms
18,664 KB
testcase_18 AC 13 ms
18,696 KB
testcase_19 AC 13 ms
18,668 KB
testcase_20 AC 18 ms
19,672 KB
testcase_21 AC 18 ms
19,656 KB
testcase_22 AC 13 ms
18,540 KB
testcase_23 AC 13 ms
18,616 KB
testcase_24 AC 13 ms
18,664 KB
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 AC 18 ms
19,564 KB
testcase_30 AC 16 ms
19,084 KB
testcase_31 AC 13 ms
18,660 KB
testcase_32 AC 18 ms
19,616 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <vector>
#include <cassert>

using int64 = long long;
using int128 = __int128_t;

const int N = 1e6 + 10;
const int mod = 1e6 + 3;
const int128 denom = 2e20;

int64 fac[mod], inv[mod];
char s[N];

int64 binom(int64 n, int64 m) {
  if (n < m) return 0;
  if (n == m || m == 0) return 1;
  int64 a = n % mod, b = m % mod;
  if (a < b) return 0;
  return fac[a] * inv[fac[b]] * inv[fac[a - b]] % mod * binom(n / mod, m / mod) % mod;
}

int main() {
  fac[0] = fac[1] = inv[1] = 1;
  for (int i = 2; i < mod; ++i) {
    fac[i] = i * fac[i - 1] % mod;
    inv[i] = (mod - mod / i) * inv[mod % i] % mod;
  }

  int64 counts[26];
  for (int i = 0; i < 26; ++i) {
    scanf("%lld", counts + i);
  }
  scanf("%s", s);
  int n = strlen(s);
  std::vector<int> lens[26];
  int freqs[26] = {};
  for (int i = 0, j; i < n; i = j) {
    for (j = i; j < n && s[i] == s[j]; ++j);
    lens[s[i] - 'a'].push_back(j - i);
    freqs[s[i] - 'a'] += j - i;
  }
  int64 ans = 1;
  for (int i = 0; i < 26; ++i) {
    if (counts[i] < freqs[i]) {
      puts("0");
      return 0;
    }
    if (freqs[i] == 0 || counts[i] == freqs[i]) {
      continue;
    }
    if (lens[i].size() == 1) {
      ans = ans * binom(counts[i], lens[i][0]) % mod;
    } else {
      int64 rest = counts[i] - freqs[i];
      int128 ok = denom + 1, ng = n * denom + 1;
      bool exact = false;
      while (ng - ok > 1) {
        int128 mid = (ok + ng) >> 1;
        int128 total = 0;
        for (auto l : lens[i]) total += (l * denom) / (mid - denom);
        if (total >= rest) {
          ok = mid;
          if (total == rest) {
            exact = true;
            ng = mid;
          }
        } else if (total < rest) {
          ng = mid;
        }
      }
      for (auto l : lens[i]) {
        int64 k = (l * denom) / (ng - denom);
        if (k) {
          ans = ans * binom(l + k, l) % mod;
          rest -= k;
        }
      }
      assert(rest >= 0);
      if (!exact) {
        for (auto l : lens[i]) {
          int64 k1 = (l * denom) / (ok - denom);
          int64 k2 = (l * denom) / (ng - denom);
          if (k1 > k2) {
            assert(k1 == k2 + 1);
            ans = ans * (k1 + l) % mod * inv[k1 % mod] % mod;
            if (--rest == 0) break;
          }
        }
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}
0