Problem:


Score : 600 points

Problem Statement

We have a grid with A horizontal rows and B vertical columns, with the squares painted white. On this grid, we will repeatedly apply the following operation:

Assume that the grid currently has a horizontal rows and b vertical columns. Choose "vertical" or "horizontal".

If we choose "vertical", insert one row at the top of the grid, resulting in an (a+1) \times b grid.

If we choose "horizontal", insert one column at the right end of the grid, resulting in an a \times (b+1) grid.

Then, paint one of the added squares black, and the other squares white.

Assume the grid eventually has C horizontal rows and D vertical columns. Find the number of ways in which the squares can be painted in the end, modulo 998244353.

Constraints

1 \leq A \leq C \leq 3000

1 \leq B \leq D \leq 3000

A, B, C, and D are integers.

Input

Input is given from Standard Input in the following format:

A B C D

Output

Print the number of ways in which the squares can be painted in the end, modulo 998244353.

Sample Input 1

1 1 2 2

Sample Output 1

3

Any two of the three squares other than the bottom-left square can be painted black.

Sample Input 2

2 1 3 4

Sample Output 2

65

Sample Input 3

31 41 59 265

Sample Output 3

387222020



Sample input:
1 1 2 2


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    a,b,c,d = LI()

    dp = [[0] * (d+1) for _ in range(c+1)]
    dp[a][b] = 1

    for i in range(a,c+1):
        for j in range(b,d+1):
            if a < i:
                dp[i][j] += dp[i-1][j] * j % mod2
            if b < j:
                dp[i][j] += dp[i][j-1] * i % mod2
            if a < i and b < j:
                dp[i][j] -= dp[i-1][j-1] * (i-1) * (j-1)

            dp[i][j] %= mod2

    return dp[c][d]


print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    A, B, C, D = map(int, input().split())
    mod = 998244353

    dp = [[0]*(D+2) for i in range(C+2)]
    dp[A][B] = 1
    for i in range(A, C+1):
        for j in range(B, D+1):
            ret = dp[i][j]
            if i-A == j-B == 1:
                ret -= (i-1)*(j-1)
            else:
                ret -= dp[i-1][j-1]*(j-1)*(i-1)
            ret %= mod
            dp[i][j] = ret
            dp[i+1][j] += ret * j
            dp[i][j+1] += ret * i

    print(dp[-2][-2])


main()

Submission status: Time Limit Exceeded

Solution code:
A, B, C, D = map(int, input().split())
mod = 998244353

dp = [[0]*(D+2) for i in range(C+2)]
dp[A][B] = 1
for i in range(A, C+1):
    for j in range(B, D+1):
        if i-A == j-B == 1:
            dp[i][j] -= (i-1)*(j-1)
        else:
            dp[i][j] -= dp[i-1][j-1]*(j-1)*(i-1)
        dp[i][j] %= mod
        dp[i+1][j] += dp[i][j] * j
        dp[i][j+1] += dp[i][j] * i

print(dp[-2][-2])

Submission status: Time Limit Exceeded

Solution code:
A,B,C,D = map(int,input().split())
MOD = 998244353

dp = [[0 for _ in range(D+1)] for _ in range(C+1)]
dp[A][B] = 1
#dp[i][j] ヨコi番目でそこまでの最大の高さがj

for i in range(A,C+1):
  for j in range(B,D+1):
    if i > A:
      dp[i][j] += dp[i-1][j]*j
    if j > B:
      dp[i][j] += dp[i][j-1]*i
    if i > A and j > B:
      dp[i][j] -= dp[i-1][j-1]*(i-1)*(j-1)
    dp[i][j] %= MOD

ans = dp[C][D]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split())
mod=998244353
dct=[[[-1]*3 for _ in range(d+1)] for _ in range(c+1)]

import sys
sys.setrecursionlimit(10**7)
def dp(i,j,bl):
  #print(i,j,bl)
  if dct[i][j][bl]>0:
    return dct[i][j][bl]
  if (i,j)==(a,b):
    return 1 if bl==0 else 0
  if i<a or j<b:
    return 0
  if i==a:
    if bl==2:
      ret=0 if j-b<2 else pow(i,j-b,mod)-pow(i-1,j-b-1,mod)*(j-b)-pow(i-1,j-b,mod)
    elif bl==1:
      ret=0 if j-b<1 else pow(i-1,j-b-1,mod)*(j-b)
    elif bl==0:
      ret=pow(i-1,j-b,mod)
  elif bl==2:
    ret=dp(i,j-1,1)+dp(i,j-1,2)*i
  elif bl==1:
    ret=(dp(i-1,j,0)+dp(i-1,j,1)+dp(i-1,j,2))*j
  else:
    ret=dp(i,j-1,0)*(i-1)
  ret%=mod
  dct[i][j][bl]=ret
  return ret

print((dp(c,d,0)+dp(c,d,1)+dp(c,d,2))%mod)

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split())
mod=998244353
dct=[[[-1]*3 for _ in range(d+1)] for _ in range(c+1)]
#from collections import defaultdict

import sys
sys.setrecursionlimit(10**7)
def dp(i,j,bl):
  #print(i,j,bl)
  if dct[i][j][bl]>0:
    return dct[i][j][bl]
  if (i,j)==(a,b):
    return 1 if bl==0 else 0
  if i<a or j<b:
    return 0
  if i==a:
    if bl==2:
      ret=0 if j-b<2 else pow(i,j-b)-pow(i-1,j-b-1)*(j-b)-pow(i-1,j-b)
    elif bl==1:
      ret=0 if j-b<1 else pow(i-1,j-b-1)*(j-b)
    elif bl==0:
      ret=pow(i-1,j-b)
  elif bl==2:
    ret=dp(i,j-1,1)+dp(i,j-1,2)*i
  elif bl==1:
    ret=(dp(i-1,j,0)+dp(i-1,j,1)+dp(i-1,j,2))*j
  else:
    ret=dp(i,j-1,0)*(i-1)
  ret%=mod
  dct[i][j][bl]=ret
  return ret

print((dp(c,d,0)+dp(c,d,1)+dp(c,d,2))%mod)
#print(dp(c,d,0),dp(c,d,1),dp(c,d,2))
#print(a,b,c,d)

Submission status: Time Limit Exceeded

Solution code:
A, B, C, D = map(int, input().split())

MOD = 998244353

dp0 = [[0] * (D + 1) for _ in range(C + 1)]
dp1 = [[0] * (D + 1) for _ in range(C + 1)]


dp0[A][B] = 1

for x in range(A, C + 1):
    for y in range(B, D + 1):
        if x == A and y == B:
            continue
        dp0[x][y] = (dp0[x][y - 1] * x + dp1[x][y - 1] * 1) % MOD
        dp1[x][y] = (dp0[x - 1][y] * y + dp1[x - 1][y] * y) % MOD

# print (dp0)
# print (dp1)        

ans = (dp0[C][D] + dp1[C][D]) % MOD
print (ans)

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int, input().split())
mod=998244353
if a==c and b==d:
  print(1)
  exit()
else:
  dp=[[0]*(d+1) for _ in range(c+1)]
  for i in range(a,c+1):
    for j in range(b,d+1):
      if i==a and j==b:
        dp[i][j]=1
      else:
        dp[i][j]=dp[i][j-1]*i+dp[i-1][j]*j-dp[i-1][j-1]*(i-1)*(j-1)
        dp[i][j]%=mod
print(dp[c][d])

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 998244353

    A, B, C, D = map(int, input().split())

    dp = [0] * B + [pow(A, i, mod) for i in range(D + 1 - B)]
    for a in range(A + 1, C + 1):
        T = [0] * (D + 1)
        for b in range(B, D + 1):
            T[b] = (a * T[b - 1] + b * dp[b] - (a - 1) * (b - 1) * dp[b - 1]) % mod
        dp = T

    print(dp[D])

main()

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

A, B, C, D = map(int, input().split())

dp = [0] * B + [pow(A, i, mod) for i in range(D + 1 - B)]
for a in range(A + 1, C + 1):
    T = [0] * (D + 1)
    for b in range(B, D + 1):
        T[b] = (a * T[b - 1] + b * dp[b] - (a - 1) * (b - 1) * dp[b - 1]) % mod
    dp = T

print(dp[D])

Submission status: Time Limit Exceeded

Solution code:
a, b, c, d = [int(x) for x in input().split()]

mod = 998244353

dp = [[0 for _ in range(d+1)] for _ in range(c+1)]

dp[a][b] = 1

for i in range(a, c+1):
	for j in range(b, d+1):
		if i == a and j == b:
			continue
		dp[i][j] = (dp[i-1][j] * j + dp[i][j-1] * i - dp[i-1][j-1] * (i-1) * (j-1)) % mod

print(dp[c][d])

Submission status: Time Limit Exceeded

Solution code:
a, b, c, d = [int(x) for x in input().split()]

mod = 998244353

dp = [[0 for _ in range(d+1)] for _ in range(c+1)]

dp[a][b] = 1

for i in range(a, c+1):
	for j in range(b, d+1):
		if i != a or j != b:
			newrow = dp[i-1][j] * j
			newcol = dp[i][j-1] * i
			common = dp[i-1][j-1] * (i-1) * (j-1)
			val = newrow + newcol - common
			dp[i][j] = val % mod

print(dp[c][d])

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 998244353

    A, B, H, W = map(int, input().split())

    dp = [[0] * (W + 1) for _ in range(H + 1)]
    dp[A][B] = 1

    for h in range(A, H + 1):
        for w in range(B, W + 1):
            if h == A and w == B: continue
            t = 0
            if h > A:
                t += dp[h - 1][w] * w
            if w > B:
                t += dp[h][w - 1] * h
            if h > A and w > B:
                t -= dp[h - 1][w - 1] * (h - 1) * (w - 1)
            dp[h][w] = t % MOD

    print(dp[H][W])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 998244353

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class Comb:
    def __init__(self, N):
        F = [1] * (N + 1)
        for i in range(N):
            F[i + 1] = (i + 1) * F[i] % mod

        self.d_inv = {}
        self.d_comb = {}
        self.F = F

    def inv(self, a):
        if a not in self.d_inv:
            self.d_inv[a] = pow(a, mod - 2, mod)
        return self.d_inv[a]

    def comb(self, a, b):
        if (a, b) not in self.d_comb:
            self.d_comb[(a, b)] = (self.F[a] * self.inv(self.F[a - b]) * self.inv(self.F[b])) % mod
            self.d_comb[(a, a - b)] = self.d_comb[(a, b)]
        return self.d_comb[(a, b)] 


def main():
    A, B, C, D = read_values()

    dp = [[0 for _ in range(D - B + 1)] for _ in range(C - A + 1)]
    dp[0][0] = 1

    for i in range(C - A):
        dp[i + 1][0] = dp[i][0] * B % mod
    for j in range(D - B):
        dp[0][j + 1] = dp[0][j] * A % mod

    for i in range(1, C - A + 1):
        for j in range(1, D - B + 1):
            dp[i][j] = dp[i - 1][j] * (B + j) + dp[i][j - 1] * (A + i) - dp[i - 1][j - 1] * (A + i - 1) * (B + j - 1) % mod

    print(dp[C - A][D - B] % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
a, b, c, d = map(int, input().split())
mod = 998244353

dp = [[0 for _ in range(d+1)] for _ in range(c+1)]
for i in range(a, c+1):
    for j in range(b, d+1):
        if i == a and j == b:
            dp[i][j] = 1
            continue
        dp[i][j] += dp[i-1][j] * j
        dp[i][j] += dp[i][j-1] * i
        dp[i][j] -= dp[i-1][j-1] * (i-1) * (j-1)
        dp[i][j] %= mod


print(dp[c][d])

Submission status: Time Limit Exceeded

Solution code:
A, B, C, D = map(int, input().split())
MOD = 998244353

dp = [[0] * (D + 2) for _ in range(C + 2)]
dp[A][B] = 1

for h in range(A, C + 1):
    for w in range(B, D + 1):
        d = dp[h][w] % MOD
        dp[h + 1][w] += d * w
        dp[h][w + 1] += d * h
        dp[h + 1][w + 1] -= d * w * h % MOD
print(dp[C][D] % MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
	a,b,c,d=map(int,input().split())
	mod=998244353
	dp=[[0 for _ in range(d)]for _ in range(c)]
	dp[a-1][b-1]=1
	for i in range(a-1,c):
		for j in range(b-1,d):
			if i!=a-1:
				dp[i][j]+=dp[i-1][j]*(j+1)%mod
			if j!=b-1:
				dp[i][j]+=dp[i][j-1]*(i+1)%mod
			if i!=a-1 and j!=b-1:
				dp[i][j]-=dp[i-1][j-1]*i*j%mod
			dp[i][j]%=mod
	print(dp[-1][-1])

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d = map(int,input().split())
ans = 0
dp = [[0]*(d+1) for i in range(c+1)]
mod = 998244353
dp[a][b] = 1
for i in range(a+1,c+1):
    dp[i][b] = dp[i-1][b] * b % mod
for i in range(b+1,d+1):
    dp[a][i] = dp[a][i-1] * a % mod
for i in range(a+1,c+1):
    for j in range(b+1,d+1):
        dp[i][j] = ((dp[i-1][j]*j) + (dp[i][j-1]*i) - (dp[i-1][j-1]*(i-1)*(j-1)))%mod
print(dp[c][d])

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split())
p=[[0]*(d+2)for i in range(c+1)]
p[a][b]=1
m=998244353
for i in range(a,c+1):
 for j in range(b,d+1):p[i][j]+=(j*p[i-1][j]+i*p[i][j-1]-(i-1)*(j-1)*p[i-1][j-1])%m;p[i][j]%=m
print(p[-1][-2]%m)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import math
import collections
import bisect


def main():
    a, b, c, d = map(int, input().split())

    dp0 = [[1 for i in range(d + 1)] for j in range(c + 1)]
    dp1 = [[0 for i in range(d + 1)] for j in range(c + 1)]
    for i in range(c + 1):
        for j in range(d + 1):
            if j < b or i < a:
                dp0[i][j] = 0
                dp1[i][j] = 0
    for i in range(a, c + 1):
        for j in range(b, d + 1):
            # print(i, j, dp[i][j])
            if a == i and b == j:
                continue
            dp0[i][j] = ((i * dp0[i][j - 1]) % 998244353 + dp1[i][j - 1]) % 998244353
            dp1[i][j] = (j * (dp0[i - 1][j] + dp1[i - 1][j]) % 998244353) % 998244353

    print((dp0[c][d] + dp1[c][d]) % 998244353)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import math
import collections
import bisect


a, b, c, d = map(int, input().split())

dp0 = [[1 for i in range(d + 1)] for j in range(c + 1)]
dp1 = [[0 for i in range(d + 1)] for j in range(c + 1)]
for i in range(c + 1):
    for j in range(d + 1):
        if j < b or i < a:
            dp0[i][j] = 0
            dp1[i][j] = 0
for i in range(a, c + 1):
    for j in range(b, d + 1):
        # print(i, j, dp[i][j])
        if a == i and b == j:
            continue
        dp0[i][j] = ((i * dp0[i][j - 1]) % 998244353 + dp1[i][j - 1]) % 998244353
        dp1[i][j] = (j * (dp0[i - 1][j] + dp1[i - 1][j]) % 998244353) % 998244353

print((dp0[c][d] + dp1[c][d]) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import math
import collections
import bisect


a, b, c, d = map(int, input().split())


dp = [[[1 for k in range(2)] for i in range(d + 1)] for j in range(c + 1)]
for k in range(2):
    for i in range(c + 1):
        for j in range(d + 1):
            dp[i][j][1] = 0
            if j < b or i < a:
                dp[i][j][k] = 0

for i in range(a, c + 1):
    for j in range(b, d + 1):
        # print(i, j, dp[i][j])
        if a == i and b == j:
            continue
        dp[i][j][0] = ((i * dp[i][j - 1][0]) % 998244353 + dp[i][j - 1][1]) % 998244353
        dp[i][j][1] = (j * (dp[i - 1][j][0] + dp[i - 1][j][1]) % 998244353) % 998244353

print((dp[c][d][0] + dp[c][d][1]) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import collections
import bisect


a, b, c, d = map(int, input().split())

dp = np.array([[[1 for k in range(2)] for i in range(d + 1)] for j in range(c + 1)])
dp[:, :, 1] = 0
dp[0:a, :, :] = 0
dp[:, 0:b, :] = 0
#dp = list(dp)

for i in range(a, c + 1):
    for j in range(b, d + 1):
        # print(i, j, dp[i][j])
        if a == i and b == j:
            continue
        dp[i][j][0] = (i * dp[i][j - 1][0] % 998244353 + dp[i][j - 1][1] % 998244353) % 998244353
        dp[i][j][1] = (j * (dp[i - 1][j][0] % 998244353 + dp[i - 1][j][1] % 998244353)) % 998244353

print((dp[c][d][0] + dp[c][d][1]) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import collections
import bisect


a, b, c, d = map(int, input().split())

dp = np.array([[[1 for k in range(2)] for i in range(d + 1)] for j in range(c + 1)])
dp[:, :, 1] = 0
dp[0:a, :, :] = 0
dp[:, 0:b, :] = 0
#dp = list(dp)

for i in range(a, c + 1):
    for j in range(b, d + 1):
        # print(i, j, dp[i][j])
        if a == i and b == j:
            continue
        dp[i][j][0] = (i * dp[i][j - 1][0] + dp[i][j - 1][1]) % 998244353
        dp[i][j][1] = (j * (dp[i - 1][j][0] + dp[i - 1][j][1])) % 998244353

print((dp[c][d][0] + dp[c][d][1]) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import collections
import bisect


a, b, c, d = map(int, input().split())

dp = np.array([[[1 for k in range(2)] for i in range(d + 1)] for j in range(c + 1)])
dp[:, :, 1] = 0
dp[0:a, :, :] = 0
dp[:, 0:b, :] = 0
dp = list(dp)

for i in range(a, c + 1):
    for j in range(b, d + 1):
        # print(i, j, dp[i][j])
        if a == i and b == j:
            continue
        dp[i][j][0] = (i * dp[i][j - 1][0] + dp[i][j - 1][1]) % 998244353
        dp[i][j][1] = (j * (dp[i - 1][j][0] + dp[i - 1][j][1])) % 998244353

print((dp[c][d][0] + dp[c][d][1]) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split())
MOD=998244353
dp=[[0]*(d-b+1) for _ in range(c-a+1)]
dp[0][0]=1
for i in range(c-a):
    dp[i+1][0]=dp[i][0]*b%MOD
for j in range(d-b):
    dp[0][j+1]=dp[0][j]*a%MOD
for i in range(c-a):
    for j in range(d-b):
        dp[i+1][j+1]=(dp[i][j+1]*(b+j+1)+dp[i+1][j]*(a+i+1)-dp[i][j]*(b+j)*(a+i))%MOD
print(dp[c-a][d-b])

Submission status: Time Limit Exceeded

Solution code:
def main():
    A, B, C, D = map(int, input().split())

    c = C - A
    d = D - B
    mod = 998244353
    dp = [[0]*(d+1) for i in range(c+1)]
    dp[0][0] = 1

    for i in range(c+1):

        for j in range(d+1):
            ret = 0
            if i == 0 and j == 0:
                continue
            if i > 0 and j > 0:
                if i == j == 1:
                    ret -= (A+i-1) * (B+j-1)
                else:
                    ret -= dp[i-1][j-1]
                    ret *= (A+i-1)*(B+j-1)
            ret += dp[i-1][j]*(B+j) + dp[i][j-1]*(A+i)

            ret %= mod
            dp[i][j] = ret
    print(dp[c][d])


main()

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split())
mod = 998244353
dp=[[0]*(d+1) for _ in range(c+1)]
dp[a][b]=1
for x in range(a,c+1):
    for y in range(b,d+1):
        if x!=a or y!=b:
            dp[x][y]=dp[x-1][y]*y+dp[x][y-1]*x-dp[x-1][y-1]*(x-1)*(y-1)
            dp[x][y]%mod
print(dp[c][d]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

A, B, C, D = MAP()

dp = [[0]*(D+1) for _ in range(C+1)]
dp[A][B] = 1

for i in range(A, C+1):
    for j in range(B, D+1):
        if j > B:
            dp[i][j] += dp[i][j-1] * i
        if i > A:
            dp[i][j] += dp[i-1][j] * j
        if A < i and B < j:
            dp[i][j] -= (i-1) * (j-1) * dp[i-1][j-1]
        dp[i][j] %= mod

print(dp[C][D])

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split());m=998244353;D=[[0]*(d+1)for _ in range(c+1)];D[a][b]=1
for i in range(c):
 for j in range(d):D[i+1][j+1]+=(D[i+1][j]*(i+1)+D[i][j+1]*(j+1)-D[i][j]*i*j)%m
print(D[c][d])

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def f(a, b):
    if a < A or b < B: return 0
    if a == A and b == B: return 1
    return (f(a-1, b) * b + f(a, b-1) * a - f(a-1, b-1) * (a - 1) * (b - 1)) % P

P = 998244353
A, B, C, D = map(int, input().split())
print(f(C, D))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    A, B, C, D = [int(x) for x in input().split()]

    MOD = 998244353

    dp = [[0] * (D - B + 1) for j in range(C - A + 1)]

    for j in range(C - A + 1):
        if j == 0:
            dp[j][0] = 1
        else:
            dp[j][0] = B ** j % MOD
        for i in range(1, D - B + 1):
            if j == 0:
                dp[j][i] = dp[j][i - 1] * (A + j) % MOD
            else:
                dp[j][i] = (dp[j][i - 1] * (A + j) + (B + i) * dp[j - 1][i] - dp[j - 1][i - 1] * (
                            (A + j - 1) * (B + i - 1))) % MOD

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    A, B, C, D = [int(x) for x in input().split()]

    MOD = 998244353

    dp = [[0] * (D - B + 1) for j in range(C - A + 1)]

    for j in range(C - A + 1):
        if j == 0:
            dp[j][0] = 1
        else:
            dp[j][0] = B ** j
        for i in range(1, D - B + 1):
            if j == 0:
                dp[j][i] = dp[j][i - 1] * (A + j)
            else:
                dp[j][i] = dp[j][i - 1] * (A + j) + (B + i) * dp[j - 1][i] - dp[j - 1][i - 1] * (
                            (A + j - 1) * (B + i - 1))

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
a, b, c, d = map(int, input().split())
MOD = 998244353

dp = [[0] * (d - b + 1) for _ in range(c - a + 1)]

dp[0][0] = 1

for x in range(1, d - b + 1):
    dp[0][x] = dp[0][x - 1] * a % MOD
for y in range(1, c - a + 1):
    dp[y][0] = dp[y - 1][0] * b % MOD

for x in range(1, c - a + 1):
    for y in range(1, d - b + 1):
        dp[x][y] = (dp[x - 1][y] * (b + y) + dp[x][y - 1] * (a + x) - dp[x - 1][y - 1] * (a + x - 1) * (b + y - 1)) % MOD

print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:

a,s,d,f=map(int,input().split())
dp=[[0]*(f+1) for i in range(d+1)]
dp[a][s]=1
mod=998244353

for x in range(a,d+1):
    for y in range(s,f+1):
        if x==a and y==s:continue
        dp[x][y]=(dp[x-1][y]*y+dp[x][y-1]*x-dp[x-1][y-1]*(x-1)*(y-1))%mod
        
print(dp[d][f])

Submission status: Time Limit Exceeded

Solution code:
def main():
    A, B, C, D = map(int, input().split())

    c = C - A
    d = D - B
    mod = 998244353
    dp = [[0]*(d+1) for i in range(c+1)]
    dp[0][0] = 1

    for i in range(c+1):
        prev = dp[i-1]
        crr = dp[i]
        if i < c:
            next = dp[i+1]
        for j in range(d+1):
            if i > 0 and j > 0:
                if i == j == 1:
                    crr[j] -= (A+i-1) * (B+j-1)
                else:
                    tmp = prev[j-1]
                    #print(tmp, i, j)
                    tmp *= (A+i-1)*(B+j-1)

                    # print(crr[j], tmp)
                    crr[j] -= tmp

            if i < c:
                next[j] += crr[j]*(B+j)
            if j < d:
                crr[j+1] += crr[j]*(A+i)
            # print(dp)
            crr[j] %= mod

    print(dp[c][d])


main()

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split())
mod=998244353
dp=[(d+1)*[0]for _ in range(c+1)]
for i in range(a,c+1):
  for j in range(b,d+1):
    if i==a and j==b:
      dp[i][j]=1
      continue
    if i==a:
      dp[i][j]=dp[i][j-1]*i%mod
      continue
    if j==b:
      dp[i][j]=dp[i-1][j]*j%mod
      continue
    dp[i][j]=(dp[i-1][j]*j+dp[i][j-1]*i-dp[i-1][j-1]*(i-1)*(j-1))%mod
print(dp[c][d])

Submission status: Time Limit Exceeded

Solution code:
def main():
    A, B, C, D = map(int, input().split())
    # 追加の仕方から考えると、塗られている数はC-A + D-B
    # 縦と横の長さが同じなら、その次の動作で塗れる組み合わせは同じ
    # 選びうる方法を全部数え上げよう

    c = C - A
    d = D - B
    mod = 998244353
    dp = [[0]*(d+1) for i in range(c+1)]
    dp[0][0] = 1

    for i in range(c+1):

        for j in range(d+1):
            if i > 0 and j > 0:
                if i == j == 1:
                    dp[i][j] -= (A+i-1) * (B+j-1)
                else:
                    tmp = dp[i-1][j-1]
                    #print(tmp, i, j)
                    tmp *= (A+i-1)*(B+j-1)

                    # print(dp[i][j], tmp)
                    dp[i][j] -= tmp

            if i < c:
                dp[i+1][j] += dp[i][j]*(B+j)
            if j < d:
                dp[i][j+1] += dp[i][j]*(A+i)
            # print(dp)
            dp[i][j] %= mod

    print(dp[c][d])


main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    MOD = 998244353

    A, B, C, D = map(int, input().split())

    dp = [[0]*(D+1) for _ in range(C+1)]
    dp[A][B] = 1
    for j in range(B+1, D+1):
        dp[A][j] = dp[A][j-1] * A % MOD
    for i in range(A+1, C+1):
        dp[i][B] = dp[i-1][B] * B % MOD

    for i in range(A+1, C+1):
        for j in range(B+1, D+1):
            dp[i][j] = (dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)) % MOD

    print(dp[C][D])


solve()

Submission status: Time Limit Exceeded

Solution code:
A, B, C, D = map(int, input().split())
# 追加の仕方から考えると、塗られている数はC-A + D-B
# 縦と横の長さが同じなら、その次の動作で塗れる組み合わせは同じ
# 選びうる方法を全部数え上げよう

c = C - A
d = D - B
mod = 998244353
dp = [[0]*(d+1) for i in range(c+1)]
dp[0][0] = 1

for i in range(c+1):
    for j in range(d+1):
        if i > 0 and j > 0:
            if i == j == 1:
                dp[i][j] -= (A+i-1) * (B+j-1)
            else:
                tmp = dp[i-1][j-1]
                #print(tmp, i, j)
                tmp *= (A+i-1)*(B+j-1)

                # print(dp[i][j], tmp)
                dp[i][j] -= tmp

        if i < c:
            dp[i+1][j] += dp[i][j]*(B+j)
        if j < d:
            dp[i][j+1] += dp[i][j]*(A+i)
        # print(dp)
        dp[i][j] %= mod

print(dp[c][d])

Submission status: Time Limit Exceeded

Solution code:
A, B, C, D = map(int, input().split())

c = C - A
d = D - B
mod = 998244353
dp = [[0]*(d+1) for i in range(c+1)]
dp[0][0] = 1

for i in range(c+1):
    for j in range(d+1):
        if i > 0 and j > 0:
            if i == j == 1:
                dp[i][j] -= (A+i-1) * (B+j-1)
            else:
                tmp = dp[i-1][j-1]
                #print(tmp, i, j)
                tmp *= (A+i-1)*(B+j-1)

                # print(dp[i][j], tmp)
                dp[i][j] -= tmp

        if i < c:
            dp[i+1][j] += dp[i][j]*(B+j)
        if j < d:
            dp[i][j+1] += dp[i][j]*(A+i)
        # print(dp)
        dp[i][j] %= mod

print(dp[c][d])

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d = map(int,input().split())
mod = 998244353
dp = [[0]*(d+1) for _ in range(c+1)]
dp[a][b] = 1
for i in range(a+1,c+1):
    dp[i][b] = dp[i-1][b]*b
    dp[i][b] %= mod
for i in range(a,c+1):
    for j in range(b+1,d+1):
        dp[i][j] += dp[i][j-1]*i+dp[i-1][j]*j-dp[i-1][j-1]*(i-1)*(j-1)
        dp[i][j] %= mod
print(dp[c][d])

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d = input().strip().split(' ')
a = int(a)
b = int(b)
c = int(c)
d = int(d)
ans = [[], []]
for i in range(a, c + 1):
  i1 = 0 if i % 2 == 0 else 1
  i2 = 0 if i1 == 1 else 1
  ans[i1] = []
  for j in range(b, d + 1):
    if a == i and j == b:
      ans[i1].append(1)
    elif a == i:
      ans[i1].append(i * ans[i1][j - b - 1])
    elif b == j:
      ans[i1].append(j * ans[i2][j - b])
    else:
      ans[i1].append(i * ans[i1][j - b - 1] + j * ans[i2][j - b] - (i - 1) * (j - 1) * ans[i2][j - b - 1])
t = 0 if c % 2 == 0 else 1
print(ans[t][d - b] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
a, b, c, d = map(int, input().split())
m = c - a + 1
n = d - b + 1
n_list = [0 for j in range(n)]
m_list = [0 for i in range(m)]

for i in range(m):
  m_list[i] = b ** i

for i in range(n):
  n_list[i] = a ** i



for i in range(1, n):
  m_list1 = m_list[:]
  m_list[0] = n_list[i]
  for j in range(1, m):
    m_list[j] = m_list1[j] * (a + j) + m_list[j - 1] * (b + i) - m_list1[j - 1] * (a + j - 1) * (b + i - 1)

print(m_list[-1] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
#import time
#it = time.time()    
#print(d[C-A][D-B] % 998244353)
A, B, C, D = map(int,input().split())

d=[[0 for j in range(D-B+1)] for i in range(C-A+1)]
d[0][0]=1
for i in range(1,C-A+1):
  d[i][0] = B*d[i-1][0] % 998244353
for j in range(1,D-B+1):
  d[0][j] = A*d[0][j-1] % 998244353
#print(time.time()-it)  
for i in range(1,C-A+1):
  for j in range(1,D-B+1):
    #d[i][j]=( (((j+B)*d[i-1][j]) + (i+A)*d[i][j-1])  - ((i+A-1)*((j+B-1)*d[i-1][j-1]) % 998244353)% 998244353)% 998244353
    d[i][j]=((((j+B)*d[i-1][j]) + (i+A)*d[i][j-1])  - ((i+A-1)*((j+B-1)*d[i-1][j-1]) ))% 998244353
    #d[i][j]=d[i-1][j-1]*((i+A)*(j+B)-1)% 998244353
#print(time.time()-it)   
print(d[C-A][D-B] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
def main():
	A,B,C,D=map(int,input().split())
	mod=998244353
	dp=[[0]*(C-A+1) for _ in range(D-B+1)]
	dp[0][0]=1
	for i in range(1,D-B+1):
		dp[i][0]=dp[i-1][0]*A%mod
	for j in range(1,C-A+1):
		dp[0][j]=dp[0][j-1]*B%mod
	for i in range(1,D-B+1):
		for j in range(1,C-A+1):
			dp[i][j]+=(dp[i-1][j]*(A+j)+dp[i][j-1]*(B+i)-((B+i-1)*(A+j-1))*dp[i-1][j-1]+mod)%mod
	print(dp[-1][-1])

if __name__=='__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
A,B,C,D=map(int,input().split())
mod=998244353
dp=[[0]*(C-A+1) for _ in range(D-B+1)]
dp[0][0]=1
for i in range(1,D-B+1):
	dp[i][0]=dp[i-1][0]*A%mod
for j in range(1,C-A+1):
	dp[0][j]=dp[0][j-1]*B%mod
for i in range(1,D-B+1):
	for j in range(1,C-A+1):
		dp[i][j]+=(dp[i-1][j]*(A+j)+dp[i][j-1]*(B+i)-((B+i-1)*(A+j-1))*dp[i-1][j-1]+mod)%mod
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
A,B,C,D=map(int,input().split())
mod=998244353
dp=[[0 for y in range(D-B+1)]for x in range(C-A+1)]
dp[0][0]=1
for x in range(C-A):
    dp[x+1][0]=(dp[x][0]*B)%mod
for y in range(D-B):
    dp[0][y+1]=(dp[0][y]*A)%mod
for x in range(C-A):
    for y in range(D-B):
        dp[x+1][y+1]=(dp[x+1][y]*(A+x))%mod
        dp[x+1][y+1]+=(dp[x][y+1]*(B+y))%mod
        dp[x+1][y+1]%=mod
        dp[x+1][y+1]-=(dp[x][y]*(A+x)*(B+y))%mod
        dp[x+1][y+1]%=mod
        dp[x+1][y+1]+=(dp[x+1][y]+dp[x][y+1])%mod
        dp[x+1][y+1]%=mod

print(dp[C-A][D-B])