Submission #58017291

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
P = 998244353
(N,M,K),*XY = $<.map{|ln| ln.split.map(&:to_i) }
V = [1,*XY.flatten].uniq.sort
E = V.each_cons(2).map.with_index{|(v0,v1),j| [v1-v0,nil,j] }<<[N+1-V[-1],nil,V.size-1]
E.rotate!(-1)
XY.each{|xy|
  i,j = xy.map{|v| V.index v }
  (E[j][1]||=[])<<i
}
D = [[1,*[0]*(V.size-1)]]
1.upto(K){|k| # (k-1,is),(k-d,j-1) -> (k,j)
  D<<E.map{|d,is,j0|
    dj = 0
    dj += D[-1].values_at(*is).sum%P if is
    dj += D[-d][j0] if d<=k
    dj %= P
  }
}
p (D[K].sum+E.sum{|d,_,j0| D[-d..-2].sum{|dk| dk[j0] }%P })%P
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

P = 998244353
(N,M,K),*XY = $<.map{|ln| ln.split.map(&:to_i) }
V = [1,*XY.flatten].uniq.sort
E = V.each_cons(2).map.with_index{|(v0,v1),j| [v1-v0,nil,j] }<<[N+1-V[-1],nil,V.size-1]
E.rotate!(-1)
XY.each{|xy|
	i,j = xy.map{|v| V.index v }
	(E[j][1]||=[])<<i
}
D = [[1,*[0]*(V.size-1)]]
1.upto(K){|k| # (k-1,is),(k-d,j-1) -> (k,j)
	D<<E.map{|d,is,j0|
		dj = 0
		dj += D[-1].values_at(*is).sum%P if is
		dj += D[-d][j0] if d<=k
		dj %= P
	}
}
p (D[K].sum+E.sum{|d,_,j0| D[-d..-2].sum{|dk| dk[j0] }%P })%P

Submission Info

Judge Result