結果

問題 No.603 hel__world (2)
コンテスト
ユーザー rickytheta
提出日時 2017-12-03 14:22:42
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 1,880 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 72 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 28,544 KB
最終ジャッジ日時 2024-11-28 10:08:30
合計ジャッジ時間 51,838 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 WA * 1 TLE * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

MOD = 1000003

def modpow(a,b)
  r = 1
  while b>0
    r = r * a % MOD if b % 2 == 1
    a = a * a % MOD
    b >>= 1
  end
  r
end
def modinv(x)
  modpow(x,MOD-2)
end

def comb(n,k)
  return 0 if k > n
  return 1 if k == n || k == 0
  ret = 1
  for i in 0...k
    ret = ret * (n-i) % MOD
  end
  for i in 1..k
    ret = ret * modinv(i) % MOD
  end
  ret
end

def solve(n,s,t)
  # n : size of t
  # s : max sum
  # t : char count in string T
  return 1 if t.length == 0
  tsum = t.inject(:+)
  return 0 if tsum > s
  return 1 if tsum == s
  # binary search
  la = 1
  lb = 1
  ha = 1048576
  hb = 1
  128.times do
    # get medium
    ta = la*hb + ha*lb
    tb = lb*hb
    if ta % 2 == 0
      ta /= 2
    else
      tb *= 2
    end
    tg = ta.gcd(tb)
    ta /= tg
    tb /= tg
    # calc xs
    xsum = 0
    for i in 0...n
      x = (t[i]*ta + tb - ta) / (ta - tb)
      if x < t[i]
        x = t[i]
      end
      xsum += x
    end
    if xsum <= s
      ha = ta
      hb = tb
    else
      la = ta
      lb = tb
    end
  end
  # (ha, hb) is threshold
  # get max
  maxa = 0
  maxb = 1
  xsum = 0
  for i in 0...n
    x = (t[i]*ha + hb - ha) / (ha - hb)
    xsum += x
    xa = x+1
    xb = x+1-t[i]
    if xa*maxb > maxa*xb
      maxa = xa
      maxb = xb
    end
  end
  # calc ans
  rest = s - xsum
  ans = 1
  for i in 0...n
    x = (t[i]*ha + hb - ha) / (ha - hb)
    xa = x+1
    xb = x+1-t[i]
    if xa*maxb == maxa*xb && rest > 0
      x += 1
      rest -= 1
    end
    ans = ans * comb(x,t[i]) % MOD
  end
  return ans
end

s = gets.chomp.split(" ").map(&:to_i)
t = "$" + gets.chomp + "$"
ans = 1
for i in 0...26
  c = (i + "a".ord).chr
  ts = []
  cnt = 0
  for j in 0...t.length
    if t[j] != c
      if cnt > 0
        ts.push(cnt)
      end
      cnt = 0
    else
      cnt += 1
    end
  end
  x = solve(ts.length, s[i], ts)
  ans = ans * x % MOD
end
puts ans
0