Problem:


Score : 400 points

Problem Statement

There are N cells arranged in a row, numbered 1, 2, \ldots, N from left to right.

Tak lives in these cells and is currently on Cell 1. He is trying to reach Cell N by using the procedure described below.

You are given an integer K that is less than or equal to 10, and K non-intersecting segments [L_1, R_1], [L_2, R_2], \ldots, [L_K, R_K].
Let S be the union of these K segments.
Here, the segment [l, r] denotes the set consisting of all integers i that satisfy l \leq i \leq r.

When you are on Cell i, pick an integer d from S and move to Cell i + d. You cannot move out of the cells.

To help Tak, find the number of ways to go to Cell N, modulo 998244353.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq K \leq \min(N, 10)

1 \leq L_i \leq R_i \leq N

[L_i, R_i] and [L_j, R_j] do not intersect (i \neq j) 

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
L_1 R_1
L_2 R_2
:
L_K R_K

Output

Print the number of ways for Tak to go from Cell 1 to Cell N, modulo 998244353.

Sample Input 1

5 2
1 1
3 4

Sample Output 1

4

The set S is the union of the segment [1, 1] and the segment [3, 4], therefore S = \{ 1, 3, 4 \} holds.

There are 4 possible ways to get to Cell 5:

1 \to 2 \to 3 \to 4 \to 5,

1 \to 2 \to 5,

1 \to 4 \to 5 and

1 \to 5.

Sample Input 2

5 2
3 3
5 5

Sample Output 2

0

Because S = \{ 3, 5 \} holds, you cannot reach to Cell 5.
Print 0.

Sample Input 3

5 1
1 2

Sample Output 3

5

Sample Input 4

60 3
5 8
1 3
10 15

Sample Output 4

221823067

Note that you have to print the answer modulo 998244353.



Sample input:
5 2
1 1
3 4


Sample output:
4

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 998244353


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, SS):
    count = [0] * (N + 10)
    count[0] = 1
    accum = [0] * (N + 10)
    accum[0] = 1

    for pos in range(1, N):
        ret = 0
        for left, right in SS:
            start = pos - right - 1
            end = pos - left
            ret += (accum[end] - accum[start])
            ret %= MOD
        count[pos] = ret
        accum[pos] = accum[pos - 1] + ret

    ret = count[N - 1]
    return ret % MOD


def main():
    # parse input
    N, K = map(int, input().split())
    SS = []
    for i in range(K):
        SS.append(tuple(map(int, input().split())))
    print(solve(N, K, SS))


# tests
T1 = """
5 2
1 1
3 4
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
4
"""

T2 = """
5 2
3 3
5 5
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
0
"""

T3 = """
5 1
1 2
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
5
"""

T4 = """
60 3
5 8
1 3
10 15
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
221823067
"""

T5 = """
10 1
1 2
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
55
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
def segfunc(x,y):return x+y
ide_ele=0
class segtree():
  def __init__(self,init_val,segfunc=segfunc,ide_ele=ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    l+=self.num
    res=self.ide_ele
    r+=self.num+1
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
mod=998244353
n,k=map(int,input().split())
l,r=[0]*k,[0]*k
for i in range(k):
  l[i],r[i]=map(int,input().split())
dp=[0]*(n+1)
dp[1]=1
st=segtree(dp)
for i in range(2,n+1):
  s=0
  for j in range(k):
    lj=max(i-r[j],0)
    rj=max(i-l[j],0)
    s+=st.query(lj,rj)
    s%=mod
  st.update(i,s)
print(s)

Submission status: Accepted

Solution code:
mod=998244353
n,k=map(int,input().split())
l,r=[0]*k,[0]*k
for i in range(k):
  l[i],r[i]=map(int,input().split())
dp=[0]*(n+1)
sumdp=[0]*(n+1)
dp[1]=1
sumdp[1]=1
for i in range(2,n+1):
  for j in range(k):
    lj=max(i-r[j],0)
    rj=max(i-l[j],0)
    dp[i]+=sumdp[rj]-sumdp[lj-1]
    dp[i]%=mod
  sumdp[i]=sumdp[i-1]+dp[i]
  sumdp[i]%=mod
print(dp[n])

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())

    LR = [list(map(int, input().split())) for _ in range(K)]
    MOD = 998244353

    dp = [0]*(N+1)
    S = [0]*(N+1)
    dp[1] = 1
    S[1] = 1

    for i in range(2, N+1):
        for l, r in LR:
            if i-l < 0:
                continue
            else:
                dp[i] += S[i-l] - S[max(i-r-1, 0)]
        dp[i] %= MOD
        S[i] = S[i-1] + dp[i]
    print(dp[-1]%MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# This code is generated by [Atcoder_base64](https://github.com/kyomukyomupurin/AtCoder_base64)
import base64
import subprocess
import zlib


exe_bin = "c%1E9e{@q-p1&_iX@NEgTA-*55euhXAQC9p3e|+B@ZzS>fiQyzKGGy@Gqy=hUZ6PaSWl?(wi9Gr*X4}Pk>l>!(b;occh2tmW1O|6NR>HzmNI8XX4DnkQBzUD6|w%H+3)whd(-z`6ZAOyr<X&%_xpL@@ArQ1_ulut@7;HMce8)JNe~DxW^xljZtx0~cQZWe%!>e4Po~4~cgTD)4S0)2&Pc}vJuS<(qw3Y0RNhFhA$lrkXbCA^gepBH#F5uSUu)*8Xw7_wj-F@jZY$C2nV6oN>A9Iar*@{tDes?!{SPqQNWDZ)EsVClEr+o_I9uh7G(hx}>wOpWrjf5-?2K+^?G=m5Y347dd>pRtingt;yS^*DtScHz^)BnJU%hN~oiiDCuAn~Ine2v*Td6#bw@Kr3CByLg)46RY9-01knOxt`CC{sW*nTF~89~|EWOCdv!UAZrFp$c_<xR<lO1a4?<#+J^iURoaMet9G;7@`B3k%@8ipXy*g8x`3jQ_j{{?j7(hehl!Eh7KJBKV3T_}n7+0>bYIeQ7Hq|LY>Sy@;JPMeu(hh3(t|_GgiK#O+YE>}+B_OjLZ=wJKi4CoIg@q#O<{S%PzPHIbx_?s!Z}%E5#zNksAmTBL9!5$T8~<wzpX($p1?MFPRLu84ZA@RjWww?q@k=FL&4ZjtLEv2d3!v_*EgLY={cBqxGVIq3^EH*W@PWm_;A4N38&oQMRweE})3Tx#C3TB52eL(v#DC)Y>gNeM(Fb-q|s_PUyPQ#{@vwMfxeGLn#ey=X8VP&HjQNRr%{i0=WVuoUd-iic1m+||0<V9>QHxi=P)_C)1Q=yy08Z*Idd^!7?Ukwh{c3wA~2z0&UGpcdQHUC5gz)f?z(D4vorq#dD<l*EX-h_p4fCmIV&n<L3ocLXnnc&H)Dp*y5d=N(deFxmw`Fo_-ET&OoF1?5O@R3_b#?oiKOhP6l0r@J7|5?W(})g6RTZD?weRyvoH4SwIcCTWGUE?;v^R#!Mzk*00iJnMXt%ehj8w`~KxI%k8H!|7pyY-ED`Vxqq#tTqk)mlDkCYMwRGe^><g7Z4`rbL-;0Gg0op*nAVf-kt2a8~#^DqZOFRUSZgSKY3^xu4HdAK6O=eI%dZAHTnXX%+tU9=R06!Dy8cvV#?jMCd{B_lgi7r50s&Qvsgyt`J1mtgIB6_xdA`KZmxO*-pAz29D1DdCl{!cum8N9*5Eb`enx}O(%@MQuD#FCYw#;I__zkI)ZljJ7skx0!FhhbWqq~==lKEgIU2l^*)JuNYaNyz4X#~udNsINgZF80?eoe34X$0U4{7jH4SraImuc`L8hpA2e_Vsl(BMyL@R=I?84X^p!3Q;Xg$92~gWEN@n0~)Z94PtQ*$yK156Y(8Nilt_Y?$O${coj%<Q83kU)usV)R6B)m9aB9D2v`h9z#8LlJajMk0Bl#r2HR|$Iy;FMfp?6<CGgaLirQOV~EENQT{0M7}~Ku%0GuZx;xfG`ClTBp&Z*q`ClN9AslO^{A0*t=*HZX|0(hqva#iqe*k$5)tH0we+_*5p?n-N70PrZs}@tz=$ftu=eZbM&9;C>yVJH{KNYquAfE4gzURt$wt50vw}|(=e;ClPIAB>+gSM3Y)dzsO2D5KZ<Z@z0uC51*PhgBkO75Mbjzo5hU0W+EBiYxG3GD!;|5e-m|ADxO&*apyKx`Pc-FN3SbZhDB)LG?R_6t-{yw&!0+X8qP9icWy+!l3E2g}6tSs^th4uFI|vuGK%Exafy!(u~LUf6y}RQ}tqyqk?sACeYy;a04ths(r<*HdR+a6C~(vJbIF9B9WOW)2}r+Y?7fzNLnfsq<8TDv2ZRGMpBwJ!la0Ys5?+UYiV|IAT`yvAto?SKbhp>;u6OZ?&ijc&l4^WgD;TQoDai9J*u{`#-Sl|Gh;YsTXbc)k5&HuU&%12f&~|bA);YUbN!RHop?C-X%7CA=^b|;yLx&NOm8{r!NV3aT_+&$y@B<m0qkUS*W?Od!Fa<_g6UKZ3kb0&Zy(iEd0saaOUpuri`W93&!02gJS5kt^YBQ$TWjXf$C25t5wX@y@<2f7dj?p%8$ARRef=wvQ$(m1vRk8Q|COHKy|MF)Q{wh<qC1Y589zqzGq$OJ@ZY^E;fmW#i281F|&5mpYaOk!KmQLc&jG>wfJfWHSr#>isp?lD?YS~>2qbG@{;e<G58gS#%~sfKA$Vr9u=cU1=6=htQ``SO=Z4@^QjY_^p}F|;9>CH0~1y7WBa~m@{Na%`$jB77>7fn6B)~DF*K2B6~x27f$|}A(_B7E8_E`IsQ;o*DgP{W6edr7dR&0vsj?k>LqK<TR677&`)dra?>XM2Ka;fMH9Lr2lg<ia#tRb&m@?afKI|vxT+=^jJE#cgvt=n2_GY?sAY%~^w`A51(Kss~E=gK!2R;EYZ^MU5_60howoRWbG53~x8?sP+Q5i{(2;PQwY?(bK6nocpf6Row`Kv{*@Qzn_w_(Dky!2PQAs@Ie9v5U6L?nG&fPN2Qzm?zkK7CKyb!8NT8+{pj@2mZdU-^Uk;)ozS)8_;+G}2<W4EdG87G)UJprVPGUyWEx?Qn~7dURqm*D$d!;}>Wv`X(^Cr_|_<`pnkL3wRse_9<3d=4t5sfLv|yDK<V|E<2t@4f64%xAmGGFe?3j16d&bqTov(FI&@v!@HekIv8m>#*i29v_Wnfs2k2c{uw5Wk?bJS%)V-O_8l5-xQnx2(ra&IFCfLFhO1Q>O1}k&Yfv0`gy!6^xbhmBgl+wcaUR`s3{&%MJ3Tu*J3Y61q+vEsTo;w>5;Gljn^F!gjV(gI^f?z_V*HtEnsYH*-bWjU(f0|*MCB;1i=r|^OdnOV?Z@b9C#H}doRYNGEB5E)l58Vr_J80VfP`Q>So<Y3ckYW^PEE2dv<hj(uI4t#qhp!Ru}@=bzQ90K^qA?wlrhnT>6bvBy9*QSGvm2jwh6Sew~wo-7TR}YN0CYI1AFoeMC{oY#?|0`Iw@9@{RJ>*|1*0X8u^cL7IC<m#mC>XuR`tYP_|@TO{1NtMthQENGr1cmJOqoCt*FwG`@x72rFi`kBT&Yw*vUg?Cq4SI!3P^D;rw~SKAM{KJY1{w~NYKV){?#TLb<~3BEZ)XRo8A@ez>9&AwRfAQ#lUm}$Hg3~d!NCG*f=!?>utEzg5TmlNgcqf5ok+?mOIw{sXrN0a|Djc=AyNB&rjW@;xuUmTh+i^_R%D0{Og92Z9?WSEpCKVb&T(O@xqeT^SkVI5ChFQyxB1_dw){**(ve*j$eXP-h;Md-rul9xeF*vaSJ$HQu#NAaCw?f6(h`7NUIg*b3`jT&U@rx?K>+L4=f+gR>mE_d7Tl;;nh@(MnH!16w4It|UT?*QH6Q7-wEi~icT>9ZXyl-aqU538l@aJ|Y+_?6H7%0;ho&XcQr4Q^KfSN->JfHe2Yp~)sc9%j#q^yv_vu}#D)`6I!eXskmD1n+Q$dV0um$J$0mPdw>ZyqJ=;j+mrAU(qXFh<8yGYZOahEumsd94`JmwmTjTJGMkRx+5_;kcdRqwk&n5zv;#sQ$1mL<*bRu<fV?5TE}hpR_thTfbDp!L;ZnkYaHtV!Z*&E+8b|N+ZF6?3kOkYb=^`2CABy0B$q2Kg&OaO$ZE^*^Jlg#Ty0*1dx7`>d*nhccLe9uC%N29xR?UPmzY7IbwE!-zBquH3Z7B$al{Up>I_gf&?A691vJZEdicAQaMxxc^xB21%S+1+38i+#aZmOD*jl3LXJL6ls+s)w$7)-|YF}@yy2UngPgx(i`KmR4v9fw0*T=okr=Sno_Z-yS0sm{j=j#ygSnX-kZ8NN8%`-jLGWrg(5B<5ouHS04=l6{7YV}iZN*}I;34Jy92_Fa1ul=B7g*OAsuYg%+wcl@AXRSJD_F5eo%Q|b#k4rq(<@ZkWSnJcJ8>}Y<^TQ=Gto49-tTpSb4v+<%b=ER*CiC9{w%w3w=~nq)TJ5)kf7qvM06z@ziV$5p&G~jjY)8a)TCDCwp*Cng!#I{;NBjPn%L$E(;odkdRKHn49y66ZP(dCwmpofRemkS$R0X*(v*c_AIZ+PJvY863{%ZwPU#dWfcPcKolm2b_wtQQ@E#DR_eE*d1m-78l?RQBn4G4PvPFCT2Y$Ds7<9ll|TR`VAp6}mY&3L}ob`_(1zm~6ce9io1A{R$`m@N`K!)MthE#Gq-WY_r~;e5vPy+Qu@RJ&)2h3|2;vVB0l7S$V`8~7gPT<-sLJ$|}W?>E=ydzrlb?-0ElEU&bG0)r+PU(f927|;DY&-iKV`e%&S?pgnT7XDq>Sa!2O-^=JjjQ%5||IX-fMt{%fJB(grbQ&9=IgBo5bhUO<_Zt+xug}YdrluPmHCx+KF*)V9!MV!0eA&tr<y=2<)jOBh)vD;%v5j9c>I;0S#V;;_g1DK;1#wG$UhDCa{Cw8q)AI9PkC*1>gB~x-&m%oPJwIRd_>BC#*5fnt_qQG|C%X#b6~tX&{LI8kS_|T~e7?}*cG6c6pOrs9pvSKuRdWjASCYZGh49LJUee>U^Z7`R&nb96m?10h{GrF;u6Go|C%^OR@vEj_m_{t*qnr`PbZvroo@9CZI)>L5!FMv8$DiZ((>Cnn42yG^;iC-S#p1k+;rLw|?eKMjAET)jP<|fSyU>yM8_P<eu>UtPJLe4_!`%#Dex)AY!tg!=9%b$J8rtop_|$QHl-U_H*!d?aKXpD7^Zx{uzk)npU|toHKTRE*I&aTXJ5%S?1u9=T#s3nMiW~i`GNGNR^Uz7Zr&f_F!+e`#!SB3N=jSRDdO3OD@pR)g6+XA{gCh6?Mere0;qxa8==lm5Up7CjEI++o#LgmE5NDaHrsVk*<|5}Sir^8zuLV2&dn;d;hb$;RH80&$#Lk07@F$DlS6S5l@^fi?@8M_>`QH`6cThW1^Yce6KE`psWG;Npq|&0!lPUR%&YyXtZ=oK))}rD@`^zka{oKs@%O9vB3~wtUpSBb}Kl5l2`KOuvp31!2w2W8^pPzZXh@CHsv^%q;Futgyu$=;%fYSDjE|+Ha%-6fU4!6Uaw|4dRHcQRk73$fT%L}=_hR|wtH?TR{>+A_8Walc-_}VJXt_DeJ-P{}q+$yc#y0IzX+q4l+6n&M2l^qeeIT|gdzQMm~oyRXp$yA%<QxCo1$s2#YBt_%VSX3sVgq)O9?d{GGnLN29$=y;2PbejcB!%NrM_0Tp*d>MKcp@nUQ@tb<@9yb}$dRz~hSd%Ag@y3sO;idd62ZL^c%Rry+7rR<h!jqBcjMt44JV;1I#EelzuD6Q9o*=}en=ZOZk3uv28!OzMDpIc(bM8<f@?bEupXeNee!YGw0`}T=71FNtn)X6)d&PXNF?7TdXgz7rIL|w(c@5VxAw44vC~vKDQCl1AD%Lp)g4)4*VrMXZ+<w;*hV-RmpX%BNqhLrD5N=ErT4@8eP<%l?ksrdOFeltDetP&oy;<J2+x-p;~Lx3ZFEI{@@vuvUJJA|@kzpuluhX_j541HQd=^~>xGY|8MW!5u~0HaXH~(YZf>{ceAs2r0O}66K|}2PnWhoEXYyzH3c50Re$5cg0%sA6o;NITKv3TpaVGb6%fU9Fazdq@ycUgt$sXd2#pQ?-`n^mJb}+6ZmU6bGqFv!-(J-N0XE51GoZ-DOu%}Wvp<dYyL5#*@I!1zPiAYxv1zD}9OU5Q4_E>dx#GwL{34Up;oQXKSi=B~9mQgyxiAfHuheA@MHx%iSC7Jf$Ihh_*8@vu}2D_sns8EA2Q-~819j4wwYt1((xDSI%VSc}($a!^M1Ot!n58AV1#`E9~gS_#z)n(A<@5h{0e}z7Nhq#!_#koFzkLI+7;e5YH`wa%mMxyQwaee;2&1nszxW6Q5^!Yx{_lW)sIDaqabiU#J-59^yiMqGL#rXR>r~JK&`)@MPJBYehlpnuRJw3whGCz&|#}DNejXk~}z$xFqGRBYhe?QY-$9TSPz^PV$ZUOy+M0*x~a{rK1<7<_1{1t;f--qDzj6vRRpbr}K`F;hb#(0$(=+6xL{Jomfg@%0;yPhR~Z_wxO8JrroVT}EMg6QvG{=UYk+c4oA2K|3A=okCDjAHG-V9@9LE}TAYXx|vmmyPYu)l-i_-gy7KO4M_)d|!0(?>toA7;oeFy-U>dyj-8ZXV=d!?5|P(V={SfVVV3p8rHrhe`xi%Ux!(rjQh{63snB8uW0{EgMR+KjgkDH3mNoyF|iHjy#GwUis`!z`O9t4FBR1GjT@$1zt(^k`mRvuk6lFGK64n?p_OE6{+O=uU0V*Y#D9z7Q?POV%qpUPYMDyy1_h)3{{iJ9@00"

open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    mod = 998244353
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = -1
    left = [0] * k
    right = [0] * k
    for i in range(k):
        left[i], right[i] = map(int, input().split())
        right[i] += 1
    for i in range(1, n + 1):
        dp[i] += dp[i - 1]
        for j in range(k):
            if i + left[j] <= n:
                dp[i + left[j]] += dp[i]
            if i + right[j] <= n:
                dp[i + right[j]] -= dp[i]
        dp[i] %= mod
    print(dp[n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 998244353


def main():
    # もらうdp + 累積和
    N, K = (int(i) for i in input().split())
    LR = [[int(i) for i in input().split()] for j in range(K)]

    dp = [0] * (N+2)
    dpsum = [0] * (N+1)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N+1):
        for le, ri in LR:
            L = max(0, i - ri - 1)
            R = i - le
            if R < 1:
                continue
            dp[i] += dpsum[R] - dpsum[L]
            dp[i] %= MOD
        dpsum[i] += dpsum[i-1] + dp[i]
        dpsum[i] %= MOD
    print(dp[N])
    # print(dpsum)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 998244353


def main():
    # 配るdp + imos法
    N, K = (int(i) for i in input().split())
    LR = [[int(i) for i in input().split()] for j in range(K)]

    dp = [0] * (N+2)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, N+1):
        for le, ri in LR:
            if i+le <= N:
                dp[i+le] += dp[i]
                dp[i+le] %= MOD
            if i+ri+1 <= N:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 累積和を用いたdpの高速か

n, k = map(int, input().split())
mod = 998244353

lr_list = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n + 1)
dp[1] = 1
sdp = [0] * (n + 1)
sdp[1] = 1
for i in range(2, n + 1):
    for j in range(k):
        right = max(0, i - lr_list[j][0])
        left = max(0, i - lr_list[j][1] - 1)
        dp[i] = (dp[i] + sdp[right] - sdp[left]) % mod
    sdp[i] = sdp[i - 1] + dp[i]

print(dp[n])

Submission status: Accepted

Solution code:

def resolve():
    MOD = 998244353
    N, K = map(int, input().split())
    S = [tuple(map(int, input().split())) for _ in range(K)]
    L = [0] * K
    R = [0] * K
    L, R = zip(*S)
    # 今回は最小回数ではなくNマスにたどり着くすべての回数
    # なので、区間の和を累積和で求める

    dp = [0] * (N + 1)
    dp[1] = 1

    dp_acum = [0] * (N + 1)
    dp_acum[1] = 1

    for i in range(2, N + 1):
        for j in range(K):
            li = i - R[j]
            ri = i - L[j]
            if ri < 0:
                continue
            li = max(li, 1)
            dp[i] += dp_acum[ri] - dp_acum[li - 1]
            dp[i] %= MOD

        dp_acum[i] = dp_acum[i - 1] + dp[i]
        dp_acum[i] %= MOD

    print(dp[N])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
p=998244353
n,k=map(int,input().split())
kukan=[]
for i in range(k):
    l,r=map(int,input().split())
    kukan.append((l,r))
dp=[0]*n
sdp=[0]*(n+1)
dp[0]=1
sdp[1]=1
for i in range(1,n):
    for l,r in kukan:
        left=max(0,i-r)
        right=max(0,i-l+1)
        dp[i]=(dp[i]+sdp[right]-sdp[left])%p
    sdp[i+1]=(sdp[i]+dp[i])%p
print(dp[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


MOD = 998244353


def main():
    N, K = MI()

    kukan = []
    for _ in range(K):
        tmp = LI()
        kukan.append(tmp)

    dp = [0] * (N + 1)
    dp[1] = 1
    dp_sum = [0] * (N+1)
    dp_sum[1] = 1

    for i in range(N+1):
        for k in range(K):
            l, r = kukan[k]
            pre_l = i - r
            pre_r = i - l
            if pre_r < 0:
                continue
            pre_l = max(pre_l, 0)
            dp[i] += dp_sum[pre_r] - dp_sum[pre_l - 1]

        dp_sum[i] = dp[i] + dp_sum[i-1]
        dp_sum[i] %= MOD
        dp[i] %= MOD

    print(dp[-1])


main()

Submission status: Accepted

Solution code:
MOD = 998244353

N, K = list(map(int, input().split()))

dp = [0] * (N+1)
dp[1] = 1

LR = []

for i in range(K):
  l, r = list(map(int, input().split()))
  LR.append([l, r])

for i in range(2, N+1):
  dp[i] = dp[i-1]
  for j in range(K):
    l, r = LR[j]
    dp[i] += dp[max(i-l, 0)] - dp[max(i-r-1, 0)]
    dp[i] %= MOD

print((dp[N]-dp[N-1]) % MOD)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
LR = [[*map(int, input().split())] for _ in range(k)]

MOD = 998244353
dp = [0]*n  # [0,n-1]
dp[0] = 1 # init
dp[1] = -1  # for Cumulative sum

for i in range(n): # i:[0,n-1]
    if i > 0: dp[i] += dp[i-1] # Cumulative sum
    for l, r in LR:
        if i+l < n:
            dp[i+l] += dp[i]
            dp[i+l] %= MOD
        if i+r+1 < n:
            dp[i+r+1] -= dp[i]
            dp[i+r+1] %= MOD

print((dp[n-1] + MOD) % MOD)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
sec = []
for i in range(k):
  l,r = map(int,input().split())
  sec.append([l,r])

mod = 998244353
dp = [0]*(n+1)
dp[0],dp[1] = 0,1
cumsum = [0]*(n+1)
cumsum[1] = 1
for i in range(2,n+1):
  for l,r in sec:
    if i>l:
      dp[i] += cumsum[i-l]-cumsum[max(0,i-r-1)]
  cumsum[i] = (dp[i]+cumsum[i-1])%mod
print(dp[n]%mod)

Submission status: Accepted

Solution code:
N,K = map(int, input().split())
d = [0]*2*K
for i in range(K):
    d[2*i], d[2*i+1] = map(int, input().split())
a=[0]*(N+1)
b=[0]*(N+1)
a[1]=1
b[1]=1
for i in range(2,N+1):
    t=0
    for j in range(K):
        if i-d[2*j]>0:
            t+=b[i-d[2*j]]
        if i-d[2*j+1]-1>0:
            t-=b[i-d[2*j+1]-1]
    a[i]=t%998244353
    b[i]=(b[i-1]+a[i])
print(a[N])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 998244353


def resolve():
    n, k = map(int, input().split())
    LR = [list(map(int, input().split())) for _ in range(k)]

    dp = [0] * (n + 1)
    dp_sum = [0] * (n + 1)
    dp[1] = 1
    dp_sum[1] = 1
    for i in range(2, n + 1):
        for l, r in LR:
            li = max(0, i - r)
            ri = i - l
            if ri < 0:
                continue
            dp[i] += dp_sum[ri] - dp_sum[li - 1]
            dp[i] %= mod
        dp_sum[i] = dp_sum[i - 1] + dp[i]
        dp_sum[i] %= mod
    print(dp[n])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n, K = [int(a) for a in input().split()]
s = [[int(a) for a in input().split()] for _ in range(K)]

MOD = 998244353

dp = [0] * (n + 1)
dp_sum = [0] * (n + 1)
dp[1] = 1

for i in range(1, n+1):
    for l, r in s:
        dp[i] += dp_sum[i-l if (i-l) > 0 else 0] - dp_sum[(i-r-1) if (i-r-1) > 0 else 0]
        dp_sum[i] = (dp[i] + dp_sum[i-1]) % MOD

print(dp[n] % MOD)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
LR = []
for _ in range(k):
    l, r = map(int, input().split())
    LR.append([l, r+1])

MOD = 998244353
dp = [0]*(n+1)  # [0,n]
dp[0] = 1
dp[1] = -1

for i in range(n): # i:[0,n-1]
    if i > 0: dp[i] += dp[i-1]
    for j in range(k):
        l, r = LR[j]
        if i+l < n:
            dp[i+l] += dp[i]
            dp[i+l] %= MOD
        if i+r < n:
            dp[i+r] -= dp[i]
            dp[i+r] %= MOD

print((dp[n-1] + MOD) % MOD)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
mod = 998244353
list_s = []
for _ in range(k):
    l, r = map(int, input().split())
    list_s.append((l, r))
dp = [0] * (n + 1)
sdp = [0] * (n + 1)
dp[1] = 1
sdp[0] = 0
sdp[1] = 1

for i in range(2, n + 1):
    for l, r in list_s:
        dl = max(0, i - r - 1)
        dr = max(0, i - l)
        dp[i] += sdp[dr] - sdp[dl]
        sdp[i] = (sdp[i - 1] + dp[i]) % mod
print(dp[n] % mod)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

mod = 998244353

n, k = map(int, input().split())
l = []
r = []
for _ in range(k):
    l_, r_ = map(int, input().split())
    l.append(l_)
    r.append(r_)
dp = [0] * (n + 1)
dp_csum = [0] * (n + 1)
dp[1] = 1
dp_csum[1] = 1
for i in range(2, n + 1):
    for j in range(k):
        left = i - r[j]
        right = i - l[j]
        if right >= 1:
            dp[i] += dp_csum[right] - dp_csum[max(left, 1) - 1]
            dp[i] %= mod
    dp_csum[i] = dp_csum[i - 1] + dp[i]
    dp_csum[i] %= mod
print(dp[-1])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(k)]

mod = 998244353

dp = [0] * (n+1)
sdp = [0] * (n+1)
dp[1] = 1
sdp[1] = 1

for i in range(n+1):
  for j in range(k):
    left = max(0, i-lr[j][1])
    right = max(0, i-lr[j][0]+1)
    
    dp[i] += sdp[right] - sdp[left]
  if i+1 <= n:
    sdp[i+1] = sdp[i]%mod + dp[i]%mod

print(dp[n]%mod)

Submission status: Accepted

Solution code:
mod = 998244353
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(k)]
for i in range(k):
    lr[i][1] += 1
dp = [0] * n
dp[0] = 1
for i in range(1, n):
    dp[i] += dp[i - 1]
    if i == 1:
        dp[1] = 0
    for l, r in lr:
        if i - l >= 0:
            dp[i] += dp[i - l]
        if i - r >= 0:
            dp[i] -= dp[i - r]
    dp[i] %= mod
print(dp[n - 1])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
L = []
for _ in range(K):
  a, b = map(int, input().split())
  L.append((a,b))
L.sort()
DP_1 = [0]*N
DP_2 = [0]*(N+1)
DP_1[0], DP_2[1] = 1, 1
mod = 998244353
for i in range(1, N):
  for l in L:
    if l[0]>i:
      break
    elif l[1]>i:
      DP_1[i] += DP_2[i-l[0]+1]
      DP_1[i] %= mod
    elif l[1]<=i:
      DP_1[i] += DP_2[i-l[0]+1]-DP_2[i-l[1]]
      DP_1[i] %= mod
  DP_2[i+1] = DP_2[i] + DP_1[i]
  DP_2[i+1] %= mod
print(DP_1[-1]%mod)

Submission status: Accepted

Solution code:
import numpy as np

m = 998244353
N, K = map(int, input().split())
span = []
for K in range(K):
    l , r = map(int, input().split())
    span.append([l, r])

add = [0,1]# 累積和
ans = [1]

for i in range(2,N+1):
    tmp = 0
    for s in span:
        l, r = s[0], s[1]+1
        if l > len(ans):
            continue
        elif r >= len(ans)+1:
            r = len(ans)+1
        tmp += (add[i-l] - add[i-r])%m
    ans.append(tmp%m)
    add.append(add[-1]+tmp)

print(ans[-1]%m)

Submission status: Accepted

Solution code:
#coding: UTF-8

N, K = map(int, input().split())
mod = 998244353
s = []
for k in range(K):
  s.append(list(map(int,input().split())))
#print(s)
cnt = [0]*N
cnt[0] = 1
sum = [0]*N
sum[0] = 1
for i in range(1,N):
  for j in range(K):
    #j個目の区間について
    if i > s[j][1]: #後ろのほう
      cnt[i] += sum[i-s[j][0]] - sum[i-s[j][1]-1]
    elif i >= s[j][0]:
      cnt[i] += sum[i-s[j][0]]
    cnt[i] = cnt[i] % mod
    sum[i] = (sum[i-1] + cnt[i])% mod
print(cnt[-1] % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env Python3

#import
#import math
#import numpy as np
#= int(input())
#= input()
modnum = 998244353

N, K = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(K)]

def mod(num):
    return num % modnum

dp = [0] * (N + 1)
sdp = [0] * (N + 1)

dp[1] = 1
sdp[1] = 1

for i in range(2, N + 1):
    for l, r in LR:
        ri = max(0, i - l)
        li = max(0, i - r - 1)

        dp[i] += sdp[ri] - sdp[li]
        dp[i] = mod(dp[i])

    sdp[i] = sdp[i - 1] + dp[i]

print(dp[N])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(K)]

dp = [0] * (N + 1)
dp_sums = [0] * (N + 1)
dp[1] = dp_sums[1] = 1

for i in range(2,N+1):
    for l, r in S: 
        if i >= r + 1:
            dp[i] += dp_sums[i - l] - dp_sums[i - r - 1] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i > l and i < r + 1:
            dp[i] += dp_sums[i - l] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i <= l:
            dp_sums[i] = dp_sums[i-1] + dp[i]
    dp[i] %= 998244353
    dp_sums[i] %= 998244353
print(dp[N])

Submission status: Accepted

Solution code:
MOD = 998244353


def main():
    N, K = (int(i) for i in input().split())
    LR = [[int(i) for i in input().split()] for j in range(K)]

    dp = [0] * (N+2)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, N+1):
        for le, ri in LR:
            if i+le <= N:
                dp[i+le] += dp[i]
                dp[i+le] %= MOD
            if i+ri+1 <= N:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
        dp[i+1] += dp[i]
        dp[i+1] %= MOD
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K = map(int, input().split())

LR = list(tuple(map(int, input().split())) for _ in range(K))

S = [0]*(N+1)
S[1] = 1

for k in range(2, N+1):
    s = 0
    for l,r in LR:
        p0,p1 = max(k-r-1, 0), max(k-l, 0)
        s += S[p1] - S[p0]

    S[k] = (S[k-1] + s)%998244353

print((S[-1] - S[-2])%998244353)

Submission status: Accepted

Solution code:
MOD = 998244353
N, K = list(map(int, input().split()))

a = [0] * (N+1)
f = [0] * (N+1)
mv = list()
for i in range(K):
    mv.append(list(map(int, input().split())))

def solve(N, a, f):
    for i in range(1, N+1):
        f[i] = (f[i-1] + a[i]) % MOD
        for j in range(len(mv)):
            l, r = mv[j]
            if i+l < N+1: a[i+l] = (a[i+l] + f[i]) % MOD
            if i+r+1 < N+1: a[i+r+1] = (a[i+r+1] - f[i]) % MOD

a[1] = 1
mv.sort()
solve(N, a, f)

print(a[N])

Submission status: Accepted

Solution code:
MOD=998244353
N,K=[int(s) for s in input().split()]
ls=[0 for _ in range(N)]
lssum=[0 for _ in range(N)]
ls[0]=1
lssum[0]=1

sections=[[int(s) for s in input().split()] for _ in range(K)]

for i in range(1,N):
  for sec in sections:
    if sec[0]>i:
      continue
    else:
      l=sec[0]
      r=min([i,sec[1]])
      ls[i]=(ls[i]+lssum[i-l]-lssum[i-r-1])%MOD
  lssum[i]=(lssum[i-1]+ls[i])%MOD
print(ls[N-1])

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n, MOD):
        self.n = n
        self.data = [0] * (n + 1)
        self.MOD = MOD

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            s %= self.MOD
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            self.data[i] %= self.MOD
            i += i & -i

    def diff(self, i, j):
        s = self.sum(j) - self.sum(i)
        s %= self.MOD
        return s


n, k = map(int, input().split())
mod = 998244353
bit = BIT(n + 2, mod)
ranges = []
for _ in range(k):
    l, r = map(int, input().split())
    ranges.append((l, r))

bit.add(1, 1)

for i in range(1, n):
    v = bit.sum(i)
    for l, r in ranges:
        bit.add(i + l, v)
        bit.add(min(n + 1, i + r + 1), -v)
print(bit.diff(n - 1, n))

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
mod = 998244353
lr = []
for k in range(K):
    lr.append(list(map(int, input().split())))
dp = [0]*(2*N+1)
dp[0] = 1
dpsum = 0
for i in range(N):
    dpsum += dp[i]%mod
    for k in lr:
        l = k[0]
        r = k[1]

        dp[i+l] += dpsum%mod
        dp[i+r+1] -= dpsum%mod
        
print(dp[N-1]%mod)

Submission status: Accepted

Solution code:
MOD=998244353
N,K=[int(s) for s in input().split()]
ls=[0 for _ in range(N)]
lssum=[0 for _ in range(N)]
ls[0]=1
lssum[0]=1

sections=[[int(s) for s in input().split()] for _ in range(K)]
sections.sort()

for i in range(1,N):
  for sec in sections:
    if sec[0]>i:
      continue
    else:
      l=sec[0]
      r=min([i,sec[1]])
      ls[i]=(ls[i]+lssum[i-l]-lssum[i-r-1])%MOD
  lssum[i]=(lssum[i-1]+ls[i])%MOD
print(ls[N-1])

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n, MOD):
        self.n = n
        self.data = [0] * (n + 1)
        self.MOD = MOD

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            s %= self.MOD
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            self.data[i] %= self.MOD
            i += i & -i


n, k = map(int, input().split())
mod = 998244353
bit = BIT(n + 2, mod)
ranges = []
for _ in range(k):
    l, r = map(int, input().split())
    ranges.append((l, r))

bit.add(1, 1)

for i in range(1, n):
    v = bit.sum(i)
    for l, r in ranges:
        bit.add(i + l, v)
        bit.add(min(n + 1, i + r + 1), -v)
print((bit.sum(n) - bit.sum(n - 1)) % mod)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
l = []
mod = 998244353
for i in range(K):
    L,R = map(int,input().split())
    l.append([L,R])
l.sort()

a = [0 for i in range(N+1)]
a[1] = 1
b = [0 for i in range(N+1)]
b[1] = 1
for i in range(2,N+1):
    for j in range(K):
        if l[j][0] < i:
            a[i] += (b[i-l[j][0]]-b[max(0,i-l[j][1]-1)])%mod
        else:
            break
    b[i] = (b[i-1]+a[i])%mod
mod = 998244353
print(a[N]%mod)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
DIV = 998244353

L = [None] * K
R = [None] * K
for i in range(K):
  L[i],R[i] = map(int,readline().split())

dp = [0] * (N + 1)
sdp = [0] * (N + 1)
dp[1] = 1
sdp[1] = 1
  
for i in range(2, len(dp)):
  for j in range(K):
    li = max(i - R[j], 0)
    ri = i - L[j]
    if ri < 0:
      continue
    dp[i] += (sdp[ri] - sdp[li - 1])
    dp[i] %= DIV
  sdp[i] = sdp[i - 1] + dp[i]
  sdp[i] %= DIV
  
print(dp[N])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
S = []
for _ in range(K):
    l, r = map(int, input().split())
    S.append((l, r))

mod = 998244353
 
dp = [0] * (N+1)
cumsum_dp = [0] * (N+1)
dp[1] = 1
cumsum_dp[1] = 1

for i in range(2, N+1):
    for s in S:
        fr = max(0, i-s[1]-1)
        to = max(0, i-s[0])
        dp[i] += (cumsum_dp[to]-cumsum_dp[fr]) % mod
    cumsum_dp[i] = (cumsum_dp[i-1] + dp[i]) % mod
    
print(dp[N]%mod)