#704165 (PyPy3) No.1696 Nonnil

提出ソース

結果

問題	No.1696 Nonnil
ユーザー	shotoyoo
提出日時	2021-10-01 23:48:50
言語	PyPy3 (7.3.15)
結果	TLE
実行時間	-
コード長	6,559 bytes
コンパイル時間	568 ms
コンパイル使用メモリ	87,056 KB
実行使用メモリ	178,176 KB
最終ジャッジ日時	2023-09-26 23:19:46
合計ジャッジ時間	6,600 ms
ジャッジサーバーID （参考情報）	judge14 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	73 ms 71,000 KB
testcase_01	AC	73 ms 70,940 KB
testcase_02	AC	82 ms 75,360 KB
testcase_03	TLE	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sys
input = lambda : sys.stdin.readline().rstrip()

write = lambda x: sys.stdout.write(x+"\n")
debug = lambda x: sys.stderr.write(x+"\n")
writef = lambda x: print("{:.12f}".format(x))

### 遅延評価セグメント木(はやい非DFS)
class LSG:
    def __init__(self,n, a=None):
        self._n = n
        self._ninf = ninf
        self._op = op
        self._mapping = mapping
        self._composition = composition
        self._f0 = f0
        x = 0
        while (1 << x) < self._n:
            x += 1
        self._log = x
        self._size = 1 << self._log
        self._d = [self._ninf] * (2 * self._size)
        self._lz = [self._f0] * self._size
        if a is not None:
            for i in range(self._n):
                self._d[self._size + i] = a[i]
            for i in range(self._size - 1, 0, -1):
                self._update(i)
    def check(self):
        return [self.query_point(p) for p in range(self._n)]
    def update_point(self, p, x):
        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        self._d[p] = x
        for i in range(1, self._log + 1):
            self._update(p >> i)
    def query_point(self, p):
        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        return self._d[p]
    def query(self, left, right):
        if left == right:
            return self._ninf
        left += self._size
        right += self._size
        for i in range(self._log, 0, -1):
            if ((left >> i) << i) != left:
                self._push(left >> i)
            if ((right >> i) << i) != right:
                self._push(right >> i)
        sml = self._ninf
        smr = self._ninf
        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1
        return self._op(sml, smr)
    def query_all(self):
        return self._d[1]
    def update(self, left, right, f):
        if right is None:
            p = left
            p += self._size
            for i in range(self._log, 0, -1):
                self._push(p >> i)
            self._d[p] = self._mapping(f, self._d[p])
            for i in range(1, self._log + 1):
                self._update(p >> i)
        else:
            if left == right:
                return
            left += self._size
            right += self._size
            for i in range(self._log, 0, -1):
                if ((left >> i) << i) != left:
                    self._push(left >> i)
                if ((right >> i) << i) != right:
                    self._push((right - 1) >> i)
            l2 = left
            r2 = right
            while left < right:
                if left & 1:
                    self._all_apply(left, f)
                    left += 1
                if right & 1:
                    right -= 1
                    self._all_apply(right, f)
                left >>= 1
                right >>= 1
            left = l2
            right = r2
            for i in range(1, self._log + 1):
                if ((left >> i) << i) != left:
                    self._update(left >> i)
                if ((right >> i) << i) != right:
                    self._update((right - 1) >> i)
    def _update(self, k):
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
    def _all_apply(self, k, f) -> None:
        self._d[k] = self._mapping(f, self._d[k])
        if k < self._size:
            self._lz[k] = self._composition(f, self._lz[k])
    def _push(self, k):
        self._all_apply(2 * k, self._lz[k])
        self._all_apply(2 * k + 1, self._lz[k])
        self._lz[k] = self._f0
    def loc(self, l, r):
        return self._lz[self._size+l : self._size+r]
    
M = 998244353
ninf = 0
f0 = None
def op(x,y):
    return (x+y)%M
def mapping(f,x):
    if f is None:
        return x
    return f
# composition: あとからきたクエリがf1に入る
def composition(f1,f2):
    if f2 is None:
        return f1
    elif f1 is None:
        return f2
    return f1

# class LSG:
#     def __init__(self, n, v):
#         self.n = n
#         self.cum = [0]
#         self.low = 0
#         self.total = 0
#         for vv in v:
#             self.cum.append(cum[-1]+vv)
#     def update(self, l, r, f):
#         if f==0:
#             # [l:r) を 0 にする
#             self.total += self.query(l,r)
#         else:
#             self.cum[r] = self.cum[r-1] + f
#     def query(self, l, r):
#         # [l,r) の区間和
#         return self.cum[r] - self.cum[l] - 
n,k = list(map(int, input().split()))
m = int(input())
lr = []
for i in range(m):
    lr.append(tuple(map(lambda i: int(i), input().split())))
index = list(range(m))
index.sort(key=lambda i: (lr[i][1], -lr[i][0]))
dp = [[0]*(k+1) for _ in range(k+1)]
dp[0][0] = 1
cum = [LSG(k+1, dp[i]) for i in range(k+1)]
low = 0
ind = 0

N = k+10 # 必要なテーブルサイズ
g1 = [0] * (N+1) # 元テーブル
g2 = [0] * (N+1) #逆元テーブル
inverse = [0] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 
for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 
def cmb(n, r, M=M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return ((g1[n] * g2[r] % M) * g2[n-r]) % M
def perm(n, r, M=M):
    if (r<0 or r>n):
        return 0
    return (g1[n] * g2[n-r]) % M

for r in range(1,k+1):
    while ind<m and lr[ind][1]<r:
        ind += 1
    for i in range(1,k+1):
#         val = 0
#         for j in range(r):
#             val += dp[i-1][j]
        val = cum[i-1].query(0,r)
        dp[i][r] = val
        cum[i].update(r,r+1, val)
    if ind<m and lr[ind][1]==r:
        ll = lr[ind][0]
        for i in range(k+1):
            cum[i].update(0,ll,0)
#             ll = lr[ind][0]
#             for j in range(ll):
#                 dp[i][j] = 0
#     print(r)
#     print(dp)
#     for i in range(k+1):
#         print(cum[i].check())
#     print()
ans = 0

for i in range(1,k+1):
#     ans += cum[i][-1] * pow(i, n, M) % M
    val = 0
    s = 1
    for j in range(i+1):
        val += cmb(i,j)*pow(i-j, n, M) * s
        s *= -1
    ans += cum[i].query(0,k+1) * val % M
    ans %= M
print(ans%M)

yukicoder

結果

テストケース

ソースコード