結果

問題 No.2792 Security Cameras on Young Diagram
ユーザー aldyasaldyas
提出日時 2024-06-22 00:12:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 121 ms / 2,000 ms
コード長 2,627 bytes
コンパイル時間 319 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 92,928 KB
最終ジャッジ日時 2024-06-24 18:48:20
合計ジャッジ時間 3,453 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 65 ms
63,616 KB
testcase_01 AC 67 ms
63,616 KB
testcase_02 AC 65 ms
63,744 KB
testcase_03 AC 72 ms
64,640 KB
testcase_04 AC 70 ms
65,408 KB
testcase_05 AC 68 ms
64,512 KB
testcase_06 AC 70 ms
65,408 KB
testcase_07 AC 68 ms
64,896 KB
testcase_08 AC 69 ms
64,512 KB
testcase_09 AC 68 ms
64,768 KB
testcase_10 AC 67 ms
64,896 KB
testcase_11 AC 69 ms
65,664 KB
testcase_12 AC 110 ms
85,632 KB
testcase_13 AC 101 ms
82,048 KB
testcase_14 AC 113 ms
85,504 KB
testcase_15 AC 88 ms
75,136 KB
testcase_16 AC 106 ms
85,888 KB
testcase_17 AC 121 ms
88,960 KB
testcase_18 AC 84 ms
73,088 KB
testcase_19 AC 88 ms
76,032 KB
testcase_20 AC 98 ms
81,152 KB
testcase_21 AC 65 ms
63,872 KB
testcase_22 AC 65 ms
63,616 KB
testcase_23 AC 117 ms
92,928 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

from collections import defaultdict, deque, Counter
from heapq import heapify, heappush, heappop, merge
from bisect import bisect_right, bisect_left 
left_binser = lower_bound = bisect_left ; right_binser = upper_bound = bisect_right
from itertools import permutations, combinations, accumulate


def precompute_factorials_and_inverses(max_n, mod):
        fact = [1] * (max_n + 1)
        inv_fact = [1] * (max_n + 1)
        for i in range(2, max_n + 1):
            fact[i] = fact[i-1] * i % mod
        inv_fact[max_n] = pow(fact[max_n], mod-2, mod)
        for i in range(max_n - 1, 0, -1):
            inv_fact[i] = inv_fact[i+1] * (i+1) % mod
        return fact, inv_fact

def comb(n, k, fact, inv_fact, mod):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % mod * inv_fact[n-k] % mod


# from math import lcm,gcd
# from math import comb, perm
# from functools import lru_cache
# from types import GeneratorType

MOD = 10**9 + 7
_MOD = 998244353

YES = "YES"
NO = "NO"
ALICE = "Alice"
BOB = "Bob"

def FLOOR_DIV(a, b) :
    return a // b
def CEIL_DIV(a, b) :
    return (a // b) + (not(not(a % b)))

def get() :
    return map(int, sys.stdin.readline().split())
def getone() :
    return int(sys.stdin.readline().strip())
def getstr() :
    return sys.stdin.readline().split()
def getonestr() :
    return sys.stdin.readline().strip()
def getarr() :
    return list(map(int, sys.stdin.readline().split()))

def _3d_ARRAY_SPAWN(i, j, k) :
    return [[[0 for _k in range(k)] for _j in range(j)] for _i in range(i)]
def _2d_ARRAY_SPAWN(i, j) :
    return [[0 for _j in range(j)] for _i in range(i)]
   
"""
"never doubt that u can't do this, cause it's an insult to ur determination"
by @deepakgoswami0552 10/03/2024
""" 

def solve() :
    ...
    # Solution here!
    f,inv_f = precompute_factorials_and_inverses(2 * 10**5, _MOD)

    n = getone()
    arr = getarr()
    arr = [arr[0]] + arr


    ans = 0
    for i in range(1, n + 1) :

        ver,hor = i - 1, arr[i] - 1
        ans = (ans + comb(ver + hor, ver, f, inv_f, _MOD)) % _MOD

        if arr[i] < arr[i - 1]:
            for hor_ in range(hor + 1, arr[i - 1]) :
                ans = (ans + comb(ver - 1 + hor_, ver - 1, f, inv_f, _MOD)) % _MOD
        

    for hor in range(0, arr[-1]) :
        ans = (ans + comb(n - 1 + hor, hor, f, inv_f, _MOD)) % _MOD

    ans %= _MOD
    return ans

""""""
testcase = ""
# testcase = "multiple" # Multiple tc


if testcase == "multiple" :

    for i in range(int(input())) : 
        print(solve())
        # solve()
        ...
else :
    print(solve())
    # solve()
    ...
0