結果
問題 |
No.1696 Nonnil
|
ユーザー |
|
提出日時 | 2025-08-06 00:38:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,214 ms / 3,500 ms |
コード長 | 2,176 bytes |
コンパイル時間 | 225 ms |
コンパイル使用メモリ | 82,356 KB |
実行使用メモリ | 131,776 KB |
最終ジャッジ日時 | 2025-08-06 00:38:36 |
合計ジャッジ時間 | 29,057 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 39 |
ソースコード
import os,sys,random,threading from random import randint,choice,shuffle from copy import deepcopy from io import BytesIO,IOBase from types import GeneratorType from functools import lru_cache,reduce from bisect import bisect_left,bisect_right from collections import Counter,defaultdict,deque from itertools import accumulate,combinations,permutations from heapq import heapify,heappop,heappush from typing import Generic,Iterable,Iterator,TypeVar,Union,List from string import ascii_lowercase,ascii_uppercase,digits from math import ceil,floor,sqrt,pi,factorial,gcd,log,log10,log2,inf from decimal import Decimal,getcontext from sys import stdin, stdout, setrecursionlimit input = lambda: sys.stdin.readline().rstrip("\r\n") MI = lambda :map(int,input().split()) li = lambda :list(MI()) ii = lambda :int(input()) mod = int(1e9 + 7) #998244353 inf = 1<<60 py = lambda :print("YES") pn = lambda :print("NO") MOD=mod = 998244353 N=10**5+1 fac = [1]*N #fac[i] i的阶乘 ifac = [1]*N #ifac[i] i的阶乘 的逆元 inv = [0]*N #inv[i] i的逆元 inv[1]=1 for i in range(2, N): fac[i] = fac[i-1]*i%mod inv[i] = (mod - mod // i) * inv[mod % i] % mod ifac[i] = ifac[i-1]*inv[i]%mod def C(n: int, k: int) -> int: #不重复组合数,n个不同物品不重复无序的取出k个 if n < 0 or k < 0 or n < k: return 0 return ((fac[n] * ifac[k]) % MOD * ifac[n - k]) % MOD def stirling2(n, k): """O(k*logn)""" res = 0 for i in range(k + 1): if (k - i) & 1: res -= C(k, i) * pow(i, n, mod) else: res += C(k, i) * pow(i, n, mod) res %= mod return res% mod m,n=li() d=[0]*(n+1) t=ii() for _ in range(t): l,r=li() d[r]=max(d[r],l) dp=[[0]*(n+1) for _ in range(n+1)] pre=[[0]*(n+1) for _ in range(n+1)] dp[0][0]=1 for i in range(n+1): pre[i][0]=1 mx=0 for i in range(1,n+1): for j in range(1,n+1): dp[i][j]=pre[i-1][j-1]-(pre[mx-1][j-1] if mx>0 else 0) pre[i][j]=(pre[i-1][j]+dp[i][j])%mod mx=max(mx,d[i]) res=0 for i in range(1,min(m,n)+1): tmp=pre[n][i]-(pre[mx-1][i] if mx>0 else 0) res+=stirling2(m,i)*tmp res%=mod print(res)