結果

問題 No.336 門松列列
ユーザー Min_25Min_25
提出日時 2016-04-23 07:47:23
言語 Python2
(2.7.18)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 2,509 bytes
コンパイル時間 248 ms
コンパイル使用メモリ 7,168 KB
実行使用メモリ 7,168 KB
最終ジャッジ日時 2024-06-12 01:12:24
合計ジャッジ時間 1,362 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
7,040 KB
testcase_01 AC 43 ms
7,040 KB
testcase_02 AC 46 ms
7,040 KB
testcase_03 AC 46 ms
7,168 KB
testcase_04 AC 45 ms
7,168 KB
testcase_05 AC 43 ms
7,040 KB
testcase_06 AC 47 ms
7,040 KB
testcase_07 AC 44 ms
6,912 KB
testcase_08 AC 45 ms
6,912 KB
testcase_09 AC 45 ms
6,912 KB
testcase_10 AC 45 ms
7,040 KB
testcase_11 AC 44 ms
7,168 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def ilog2(n):
  return 0 if n <= 0 else n.bit_length() - 1

def pack(pack, shamt):
  size = len(pack)
  while size > 1:
    npack = []
    for i in range(0, size - 1, 2):
      npack += [pack[i] | (pack[i+1] << shamt)]
    if size & 1:
      npack += [pack[-1]]
    pack, size, shamt = npack, (size + 1) >> 1, shamt << 1
  return pack[0]

def unpack(M, size, shamt):
  s, sizes = size, []
  while s > 1:
    sizes += [s]
    s = (s + 1) >> 1
  ret = [M]
  for size in sizes[::-1]:
    mask, nret = (1 << shamt) - 1, []
    for c in ret:
      nret += [c & mask, c >> shamt]
    ret, shamt = nret[:size], shamt >> 1
  return ret

def poly_mul_mod(f, g, mod):
  size = min(len(f), len(g))
  shift = ((mod - 1) ** 2 * size).bit_length()
  rsize = len(f) + len(g) - 1
  h = unpack(pack(f, shift) * pack(g, shift), rsize, shift * (1 << ilog2(rsize - 1)))
  return [int(x % mod) for x in h]

def poly_inverse_mod(f, size, mod):
  assert(f[0] == 1)
  deg, degs = size - 1, []
  while deg > 0:
    degs += [deg]
    deg >>= 1

  f2 = f[:]
  if len(f2) < size:
    f2.extend([0] * (size - len(f2)))

  inv = [1]
  for t in degs[::-1]:
    s = t + 1 - len(inv)
    tmp = poly_mul_mod(f2[:t + 1], inv, mod)[len(inv):]
    tmp = poly_mul_mod(tmp[:s], inv[:s], mod)
    inv.extend([-v % mod for v in tmp[:s]])
  return inv

def mod_invs(N, mod):
  ret = [1] * (N + 1)
  for i in range(2, N + 1):
    ret[i] = ret[mod % i] * (mod - mod // i) % mod
  return ret

def facts_mod(size, p):
  facts = [1] * (size + 1)
  ifacts = [1] * (size + 1)
  for i in range(1, size + 1):
    facts[i] = facts[i-1] * i % p
  ifacts[size] = pow(facts[size], p - 2, p)
  for i in range(size, 1, -1):
    ifacts[i-1] = ifacts[i] * i % p
  return facts, ifacts

def prob336():
  N = 2016
  MOD = 10 ** 9 + 7

  invs = mod_invs(N + 1, MOD)
  facts, ifacts = facts_mod(N + 1, MOD)
  inv2 = invs[2]

  E = [0 if i & 1 else ifacts[i] for i in range(N + 1)]
  E = poly_inverse_mod(E, N + 1, MOD)
  E = [c * facts[i] % MOD for i, c in enumerate(E)]

  B = poly_inverse_mod(ifacts[1:], N + 1, MOD)
  B = [c * facts[i] % MOD for i, c in enumerate(B)]
  T = [pow(2, i, MOD) for i in range(N + 1)]

  A = [0] * (N + 1)
  for i in range(0, N + 1, 2):
    A[i] = (-1) ** (i // 2) * E[i] * 2 % MOD

  for i in range(1, N + 1, 2):
    t = (-1) ** ((i - 1) // 2)
    A[i] = 2 * t * T[i + 1] * (T[i + 1] - 1) % MOD * B[i + 1] % MOD * invs[i + 1] % MOD

  from sys import stdin
  for line in stdin:
    n = int(line)
    print(0 if n <= 2 else A[n])

prob336()
0