結果
問題 | No.1102 Remnants |
ユーザー |
![]() |
提出日時 | 2020-07-03 22:34:17 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,626 bytes |
コンパイル時間 | 480 ms |
コンパイル使用メモリ | 81,708 KB |
実行使用メモリ | 150,424 KB |
最終ジャッジ日時 | 2023-10-17 05:35:46 |
合計ジャッジ時間 | 12,599 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 345 ms
109,372 KB |
testcase_01 | AC | 348 ms
109,372 KB |
testcase_02 | AC | 374 ms
109,384 KB |
testcase_03 | AC | 353 ms
109,380 KB |
testcase_04 | AC | 345 ms
109,380 KB |
testcase_05 | RE | - |
testcase_06 | AC | 369 ms
112,788 KB |
testcase_07 | RE | - |
testcase_08 | AC | 350 ms
109,640 KB |
testcase_09 | AC | 353 ms
109,640 KB |
testcase_10 | AC | 352 ms
109,636 KB |
testcase_11 | AC | 355 ms
109,652 KB |
testcase_12 | AC | 352 ms
109,664 KB |
testcase_13 | AC | 355 ms
109,664 KB |
testcase_14 | AC | 394 ms
126,808 KB |
testcase_15 | AC | 384 ms
122,324 KB |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | AC | 382 ms
121,264 KB |
testcase_20 | AC | 359 ms
110,392 KB |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | AC | 396 ms
125,484 KB |
testcase_25 | RE | - |
testcase_26 | AC | 355 ms
109,612 KB |
testcase_27 | AC | 372 ms
117,564 KB |
ソースコード
MOD = 10**9+7 k = 72 kk = k // 4 K = 1<<k nu = lambda L: int("".join([hex(K+a)[3:] for a in L[::-1]]), 16) st = lambda n: hex(n)[2:] li = lambda s, l, r: [int(a, 16) % P if len(a) else 0 for a in [s[-(i+1)*kk:-i*kk] for i in range(l, r)]] def grow(d, v, h): h += [0] * d f = [(-1 if (i+d) % 2 else 1) * fainv[i] * fainv[d-i] % P * h[i] % P for i in range(d+1)] nuf = nu(f) a = d * inv[v] % P t = [1] * (3*d+3) for i in range(1, 3*d+3): t[i] = t[i-1] * (a - d + i - 1) % P ti = [1] * (3*d+3) ti[-1] = pow(t[-1], P-2, P) for i in range(1, 3*d+3)[::-1]: ti[i-1] = ti[i] * (a - d + i - 1) % P iv = [1] * (3*d+3) for i in range(1, 3*d+3): iv[i] = ti[i] * t[i-1] % P ### g = [inv[i] for i in range(1, 2*d+2)] fg = li(st(nuf * nu(g)), d, d * 2 + 1) for i in range(d): h[i+d+1] = fg[i] * fa[d+i+1] % P * fainv[i] % P ### g = [iv[i] for i in range(1, 2*d+2)] fg = li(st(nuf * nu(g)), d, d * 2 + 1) for i in range(d+1): h[i] = h[i] * (fg[i] * t[d+i+1] % P * ti[i] % P) % P ### g = [iv[i] for i in range(d+2, 3*d+3)] fg = li(st(nuf * nu(g)), d, d * 2 + 1) for i in range(d): h[i+d+1] = h[i+d+1] * (fg[i] * t[2*d+i+2] % P * ti[d+i+1] % P) % P return h # Create a table of the factorial of the first v+2 multiples of v, i.e., [0!, v!, 2v!, ..., (v(v+1))!] def create_table(v): s = 1 X = [1, v+1] while s < v: X = grow(s, v, X) s *= 2 table = [1] for x in X: table.append(table[-1] * x % P) return table def fact(i, table): a = table[i//v] for j in range(i//v*v+1, i+1): a = a * j % P return a P = 10**9+7 N = 10**8 v = 1 << (N.bit_length() + 1) // 2 fa = [1] * (2*v+2) fainv = [1] * (2*v+2) for i in range(2*v+1): fa[i+1] = fa[i] * (i+1) % P fainv[-1] = pow(fa[-1], P-2, P) for i in range(2*v+1)[::-1]: fainv[i] = fainv[i+1] * (i+1) % P inv = [0] * (2*v+2) for i in range(1, 2*v+2): inv[i] = fainv[i] * fa[i-1] % P T = create_table(v) C = lambda n, k: fact(n, T) * pow(fact(k, T) * fact(n-k, T), P-2, P) % P inverse = [0, 1] g1 = [1, 1] g2 = [1, 1] for i in range( 2, 10**5 + 1 ): g1.append( ( g1[-1] * i ) % MOD ) inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD ) g2.append( (g2[-1] * inverse[-1]) % MOD ) # N, M = map(int, input().split()) X = list(map(int, input().split())) #print(len(fa), fa[:10]) # aa = fact(M, T) Y = [aa] for i in range(N-1): Y.append(Y[-1]*(M+i+1)%MOD) iM = pow(aa, P-2, P) R = 0 for i in range(N): R = (R + X[i]*Y[i]*Y[N-i-1]*iM*iM*g2[i]*g2[N-i-1]) % P print(R)