結果

問題 No.1696 Nonnil
ユーザー shotoyooshotoyoo
提出日時 2021-10-01 23:48:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 6,559 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 177,432 KB
最終ジャッジ日時 2024-07-19 17:05:23
合計ジャッジ時間 5,703 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
59,392 KB
testcase_01 AC 42 ms
54,272 KB
testcase_02 AC 53 ms
63,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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0