結果

問題 No.603 hel__world (2)
コンテスト
ユーザー zimpha
提出日時 2017-12-03 02:25:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,353 bytes
コンパイル時間 525 ms
コンパイル使用メモリ 52,856 KB
最終ジャッジ日時 2025-01-05 04:43:28
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 RE * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:33:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   33 |     scanf("%lld", counts + i);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
main.cpp:35:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   35 |   scanf("%s", s);
      |   ~~~~~^~~~~~~~~

ソースコード

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