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:
MOD = 998244353
HALF = (MOD + 1) // 2


def solve(a, b, c, d):
    dp1 = [[0] * (d + 1) for _ in range(c + 1)]
    dp2 = [[0] * (d + 1) for _ in range(c + 1)]
    dp3 = [[0] * (d + 1) for _ in range(c + 1)]
    dp1[a][b] = 1
    dp2[a][b] = 0
    dp3[a][b] = 0
    for i in range(a + 1, c + 1):
        dp1[i][b] = (pow(b - 1, i - a, MOD) + pow(b - 1, i - a - 1, MOD) * 1 * (i - a)) % MOD
        dp3[i][b] = (pow(b, i - a, MOD) - dp1[i][b]) % MOD
    for j in range(b + 1, d + 1):
        dp1[a][j] = (pow(a - 1, j - b, MOD) + pow(a - 1, j - b - 1, MOD) * 1 * (j - b)) % MOD
        dp2[a][j] = (pow(a, j - b, MOD) - dp1[a][j]) % MOD
    for i in range(a + 1, c + 1):
        for j in range(b + 1, d + 1):
            dp1[i][j] = (((dp1[i - 1][j] + dp2[i - 1][j]) * (j - 1) + (dp1[i][j - 1] + dp3[i][j - 1]) * (i - 1)) * HALF) % MOD
            dp2[i][j] = (dp2[i][j - 1] * i + dp1[i][j - 1] + dp3[i][j - 1]) % MOD
            dp3[i][j] = (dp3[i - 1][j] * j + dp1[i - 1][j] + dp2[i - 1][j]) % MOD

    # print(dp1, dp2, dp3)
    # print((dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD)
    return (dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD


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


def test():
    assert solve(1, 1, 2, 2) == 3
    assert solve(1, 1, 3, 3) == 30
    assert solve(2, 1, 3, 4) == 65
    # assert solve(31, 41, 59, 265) == 387222020


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

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

data[1][1]=1

#print(data)

for i in range(1,n):
    gyou=a+i-1
    for j in range(1,m):
        retu=b+j-1
        if(i*j==1):
            continue
        data[i][j]=data[i-1][j]*retu+data[i][j-1]*gyou-data[i-1][j-1]*(gyou-1)*(retu-1)%p
        #print(gyou,retu,i,j,data[i][j])
#print(data)
print(data[n-1][m-1]%p)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    A, B, C, D = map(int, input().strip().split())

    ans_mat = [[0 for i in range(D)] for j in range(C)]

    ans_mat[A - 1][B - 1] = 1


    def f(x, y):
        return ans_mat[x][y - 1] * (x + 1) + ans_mat[x - 1][y] * (y + 1) \
               - ans_mat[x - 1][y - 1] * x * y


    for i in range(A-1, C):
        for j in range(B-1, D):
            if not i == A-1 or not j == B-1:
                ans_mat[i][j] = f(i, j)
    print(ans_mat[-1][-1]%998244353)

Submission status: Time Limit Exceeded

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

dp=[[0]*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 and j==B-1:
            continue
        if i>A-1:
            dp[i][j]+=dp[i-1][j]*(j+1)
        if j>B-1:
            dp[i][j]+=dp[i][j-1]*(i+1)
        if i>A-1 and j>B-1:
            dp[i][j]-=dp[i-1][j-1]*(j)*(i)
        dp[i][j]%=mod

print(dp[C-1][D-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

MOD = 998244353
A,B,C,D= map(int,input().split())
#A,B,C,D = 1,1,100,100

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

memo = dpinit((C+1,D+1))
memo[A][B] = 1
for Y in range(A,C+1):
    memo[Y][1] = 1
for X in range(B,D+1):
    memo[1][X] = 1

def cnt(C,D):
    if memo[C][D] != 0:
        return memo[C][D]
    res = 0
    if C > A:
        res += (D * cnt(C-1,D) % MOD)
    if D > B:
        res += (C * cnt(C,D-1) % MOD)
    if C > A and D > B:
        res -= (cnt(C-1,D-1)*(C-1)*(D-1) % MOD)
    res %= MOD
    memo[C][D] = res 
    return res

print(cnt(C,D))

Submission status: Time Limit Exceeded

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

print(dp[c][d])

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


import copy

for i in range(1,n) :
  m_list1=copy.copy(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:
mod = 998244353
a,b,c,d = map(int,input().split())
dp = [[0 for _ in range(d+1)] for _ in range(c+1)]

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

for i in range(a+2,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][j-1] * i % mod + dp[i-1][j] * j % mod - dp[i-1][j-1]*(i-1)*(j-1)%mod

#print(dp)
print(dp[c][d] % mod)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

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

@lru_cache(maxsize=None)
def count(H, W):
    if H == A and W == B:
        return 1

    if H == A and W > B:
        return count(A, W - 1) * A % MOD
    if H > A and B == W:
        return count(H - 1, B) * B % MOD

    ret = 0
    ret += count(H - 1, W) * W
    ret += count(H, W - 1) * H
    ret -= count(H - 1, W - 1) * (W - 1) * (H - 1)

    return ret % MOD

print(count(C, D))

Submission status: Time Limit Exceeded

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

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

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 % MOD

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):
    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)) % MOD

print(dp[c][d])

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
HALF = (MOD + 1) // 2


def solve(a, b, c, d):
    dp1 = [[0] * (d + 1) for _ in range(c + 1)]
    dp2 = [[0] * (d + 1) for _ in range(c + 1)]
    dp3 = [[0] * (d + 1) for _ in range(c + 1)]
    dp1[a][b] = 1
    dp2[a][b] = 0
    dp3[a][b] = 0
    for i in range(a + 1, c + 1):
        dp1[i][b] = (pow(b - 1, i - a, MOD) + pow(b - 1, i - a - 1, MOD) * 1 * (i - a)) % MOD
        dp3[i][b] = (pow(b, i - a, MOD) - dp1[i][b]) % MOD
    for j in range(b + 1, d + 1):
        dp1[a][j] = (pow(a - 1, j - b, MOD) + pow(a - 1, j - b - 1, MOD) * 1 * (j - b)) % MOD
        dp2[a][j] = (pow(a, j - b, MOD) - dp1[a][j]) % MOD
    for i in range(a + 1, c + 1):
        for j in range(b + 1, d + 1):
            dp1[i][j] = (((dp1[i - 1][j] + dp2[i - 1][j]) * (j - 1) + (dp1[i][j - 1] + dp3[i][j - 1]) * (i - 1)) * HALF) % MOD
            dp2[i][j] = (dp2[i][j - 1] * i + dp1[i][j - 1] + dp3[i][j - 1]) % MOD
            dp3[i][j] = (dp3[i - 1][j] * j + dp1[i - 1][j] + dp2[i - 1][j]) % MOD

    # print(dp1, dp2, dp3)
    # print((dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD)
    return (dp1[c][d] + dp2[c][d] + dp3[c][d]) % MOD


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


def test():
    assert solve(1, 1, 2, 2) == 3
    assert solve(1, 1, 3, 3) == 30
    assert solve(2, 1, 3, 4) == 65
    assert solve(31, 41, 59, 265) == 387222020


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod=998244353
    a,b,c,d=map(int,input().split())
    x=[[[0,0] for i in range(d+1)] for i in range(c+1)]

    x[a][b]=[1,0]
    for j in range(b+1,d+1):
        x[a][j][0]=x[a][j-1][0]*a%mod

    for i in range(a+1,c+1):
        p=x[i-1][b][0]*b%mod
        x[i][b]=[p,p]
        for j in range(b+1,d+1):
            p,q,r= x[i-1][j][0],x[i][j-1][0], x[i][j-1][1]
            x[i][j]=[(p*j+(q-r)*i+r)%mod, x[i-1][j][0]*j %mod]
    print(x[c][d][0]%mod)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

dp = [[1 for i in range(d+1)] for j in range(c+1)]

mod = 998244353

for y in range(c+1):
    if y < a:
        continue
    for x in range(d+1):
        if x < b:
            continue
        if y == a and x == b:
            continue
        py = 0
        px = 0
        m = 0
        if y > a:
            py = dp[y-1][x] * x
        if x > b:
            px = dp[y][x-1] * y
        if y > a and x > b:
            m = dp[y-1][x-1] * (y-1) * (x-1)
        dp[y][x] = py + px - m
        dp[y][x] %= mod


print(dp[c][d])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

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

dp = [[-1]*3001 for i in range(3001)]

for i in range(a+1):
	for j in range(b+1):
		dp[i][j] = 1

mod = 998244353

def num(x,y):
	if x == a and y == b:
		return 0
	elif x < a or y < b:
		return 0
	return solv(x,y)

def solv(x,y):
	if x < a or y < b:
		return 0
	if dp[x][y] >= 0:
		return dp[x][y]
	x_ = (solv(x-1,y) * y) % mod
	y_ = (solv(x,y-1) * x) % mod

	ref = (x_ + y_)%mod
	if solv(x-1,y) == 0 or solv(x,y-1) == 0:
		dp[x][y] = ref
		return ref
	ref %= mod
	ref += mod
	ref -= ((((x-1)*(y-1)) % mod) * solv(x-1,y-1)) % mod
	
	ref %= mod
	dp[x][y] = ref
	return ref

print(solv(c,d))

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
mod=998244353
a,b,c,d=map(int,input().split())
x=[[[0,0] for i in range(d+1)] for i in range(c+1)]

x[a][b]=[1,0]
for j in range(b+1,d+1):
    x[a][j][0]=x[a][j-1][0]*a%mod

for i in range(a+1,c+1):
    p=x[i-1][b][0]*b%mod
    x[i][b]=[p,p]
    for j in range(b+1,d+1):
        x[i][j][0]=( x[i-1][j][0]*j + (x[i][j-1][0]-x[i][j-1][1])*i + x[i][j-1][1] )%mod
        x[i][j][1]=x[i-1][j][0]*j %mod
print(x[c][d][0]%mod)

Submission status: Time Limit Exceeded

Solution code:
A, B, C, D = list(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 % MOD
for i in range(B + 1, D + 1):
  DP[A][i] = DP[A][i - 1] * A % MOD

N = (C - A) + (D - B) + 1
for i in range(2, N):
  s = max(0, i - (D - B))
  g = min(i, C - A + 1)
  for j in range(s, g):
    x = A + j
    y = B + i - j
    DP[x][y] = (DP[x-1][y] * y + DP[x][y-1] * x) % MOD
    DP[x][y] -= DP[x-1][y-1] * (x - 1) * (y - 1)
    while DP[x][y] < 0:
      DP[x][y] += 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):
  ans.append([])
  for j in range(b, d + 1):
    if a == i and j == b:
      ans[i - a].append(1)
    elif a == i:
      ans[i - a].append(i * ans[i - a][j - b - 1])
    elif b == j:
      ans[i - a].append(j * ans[i - a - 1][j - b])
    else:
      ans[i - a].append(i * ans[i - a][j - b - 1] + j * ans[i - a - 1][j - b] - (i - 1) * (j - 1) * ans[i - a - 1][j - b - 1])
print(ans[c - a][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 i in range(m)] for j in range(n)]
n_list[0][0]=1
for i in range(1,m) :
  n_list[0][i]=n_list[0][i-1]*b

for i in range(1,n) :
  n_list[i][0]=n_list[i-1][0]*a


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



print(n_list[-1][-1]%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    mod = 998244353
    
    a, b, c, d = map(int, input().split())
    dp = dict()
    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 j == b:
                dp[(i, j)] = dp[(i-1, j)]*j%mod
                continue
            if i == a:
                dp[(i, j)] = dp[(i, j-1)]*i%mod
                continue
            dp[(i, j)] = (dp[(i-1, j)]*j+dp[(i, j-1)]*i+mod-dp[(i-1, j-1)]*(i-1)*(j-1))%mod
    print(dp[(c, d)])        
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    mod = 998244353
    
    a, b, c, d = map(int, input().split())
    dp = dict()
    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 j == b:
                dp[(i, j)] = dp[(i-1, j)]*j%mod
                continue
            if i == a:
                dp[(i, j)] = dp[(i, j-1)]*i%mod
                continue
            dp[(i, j)] = (dp[(i-1, j)]*j+dp[(i, j-1)]*i+mod-dp[(i-1, j-1)]*(i-1)*(j-1))%mod
    print(dp[(c, d)])        
            

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

DP = np.zeros([C+1,D+1],dtype=np.int32)
DP[A,B] = 1
for a in range(A+1,C+1):
    DP[a,B] = DP[a-1, B] * B % P
for b in range(B+1,D+1):
    DP[A,b] = DP[A, b-1] * A % P
for a in range(A+1,C+1):
    for b in range(B+1,D+1):
        DP[a,b] = (b*DP[a-1,b] + a*DP[a,b-1] - (a-1)*(b-1)*DP[a-1,b-1]) % P

print(DP[C,D])

Submission status: Time Limit Exceeded

Solution code:
a,b,c,d=map(int,input().split())
mod = 998244353
dp=[[0 for i in range(d+1)] for j in range(c+1)]
dp[a][b]=1
if a>c or b>d:
    print(0)
    exit()
#a<=c and b<=d:
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:
a, b, c, d = map(int, input().split())
dp = [[1 for _ in range(d - b + 1)] for _ in range(c - a + 1)]

mod = 998244353
for x in range(c - a + 1):
    for y in range(d - b + 1):
        if x == 0:
            if y > 0:
                dp[x][y] = dp[x][y - 1] * (a + x) % mod
        elif y == 0:
            dp[x][y] = dp[x - 1][y] * (b + y) % mod
        else:
            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,b,c,d = map(int,input().split())
mod = 998244353

dp = [[None]*(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 %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):
    if dp[i][j]:
      continue
    tmp = dp[i-1][j-1]*(i-1)*(j-1) %mod
    dp[i][j] = (dp[i-1][j]*j+dp[i][j-1]*i - tmp) %mod

print(dp[c][d])

Submission status: Time Limit Exceeded

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

dp = [[None]*(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 %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):
    if dp[i][j]:
      continue
    tmp = dp[i-1][j-1]*(i-1)*(j-1)
    dp[i][j] = (dp[i-1][j]*j+dp[i][j-1]*i - tmp) %mod

print(dp[c][d])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from functools import lru_cache
INF = float("inf")

MOD = 998244353  # type: int


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

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

    print(f(C, D))

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from functools import lru_cache
INF = float("inf")

MOD = 998244353  # type: int


def main():
    A, B, C, D = map(int, input().split())
    DP = [[None]*(D-B) for _ in range(C-A)]

    def f(a, b):
        if a < A or b < B:
            return 0
        if a == A and b == B:
            return 1
        elif a == A:
            return pow(A, b-B, MOD)
        elif b == B:
            return pow(B, a-A, MOD)
        ans = (f(a-1, b)*b) % MOD
        ans += (f(a, b-1)*a) % MOD
        ans -= (f(a-1, b-1)*(a-1)*(b-1)) % MOD
        ans %= MOD
        return ans

    print(f(C, D))

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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
  
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]) % 998244353 + (i+A)*d[i][j-1] % 998244353 - ((i+A-1)*((j+B-1)*d[i-1][j-1]) % 998244353)% 998244353
    
print(d[C-A][D-B] % 998244353)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from functools import lru_cache
INF = float("inf")

MOD = 998244353  # type: int


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

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

    print(f(C, D))

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

DP = {}
DP[A,B] = 1
for a in range(A+1,C+1):
    DP[a,B] = DP[a-1, B] * B % P
for b in range(B+1,D+1):
    DP[A,b] = DP[A, b-1] * A % P
for a in range(A+1,C+1):
    for b in range(B+1,D+1):
        DP[a,b] = (b*DP[a-1,b] + a*DP[a,b-1] - (a-1)*(b-1)*DP[a-1,b-1]) % P

print(DP[C,D])

Submission status: Time Limit Exceeded

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

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

print(dp[A][B][0])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

memo = {(A,B):1}
for Y in range(A,C+1):
    memo[(Y,1)] = 1
for X in range(B,D+1):
    memo[(1,X)] = 1

def cnt(C,D):
    if (C,D) in memo:
        return memo[(C,D)]
    res = 0
    if C > A:
        res += D * cnt(C-1,D)
    if D > B:
        res += C * cnt(C,D-1)
    if C > A and D > B:
        res -= cnt(C-1,D-1)*(C-1)*(D-1)
    res %= MOD
    memo[(C,D)] = res 
    return res

print(cnt(C,D))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    A, B, C, D = map(int, input().split())
    mod = 998244353
    DP = defaultdict(int)
    DP[(A, B)] = 1
    for cb in range(B + 1, D + 1):
        DP[(A, cb)] = (DP[(A, cb - 1)] * A) % mod

    for ca in range(A + 1, C + 1):
        DP[(ca, B)] = (DP[(ca - 1, B)] * B) % mod
        for nb in range(B + 1, D + 1):
            DP[(ca, nb)] = (DP[(ca, nb - 1)] * ca + DP[(ca - 1, nb)] * nb - DP[(ca - 1, nb - 1)] * (ca - 1) * (nb - 1)) % mod

    print(DP[(C, D)])
    #print(DP)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""
dp、無理な組み合わせを引く、追加された黒マスの数は決まっている
各マスのdp
下から来たものと左から来たものをdpで保持
下から来たものは次だけ制約あり
dp = [下から、左から]
"""
MOD = 998244353
A, B, C, D = lr()  # Cは縦
dp = [[[0, 0] for _ in range(D+1)] for _ in range(C+1)]   # 1-indexed
dp[A][B] = [0, 1]
for i in range(A, C+1):
    for j in range(B, D+1):
        # iが縦
        if i == A and j == B:
            continue
        if i > A:
            dp[i][j][0] = sum(dp[i-1][j]) * j
        if j > B:
            dp[i][j][1] = dp[i][j-1][0] + dp[i][j-1][1] * i
        dp[i][j][0] %= MOD
        dp[i][j][1] %= MOD

answer = sum(dp[C][D])
print(answer%MOD)

Submission status: Time Limit Exceeded

Solution code:
def read_int():
    return int(input())


def read_ints():
    return map(int, input().split(' '))


mod = 998244353


def fexp(x, y):
    ans = 1
    while y > 0:
        if (y & 1) > 0:
            ans = ans * x % mod
        x = x * x % mod
        y >>= 1
    return ans


a, b, c, d = read_ints()
dp = [[0 for j in range(d + 1)] for i in range(c + 1)]
dp[a][b] = 1
for i in range(a + 1, c + 1):
    dp[i][b] = dp[i - 1][b] * b % mod
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):
    for j in range(b + 1, d + 1):
        dp[i][j] = (dp[i - 1][j] * j + dp[i][j - 1]
                    * i - (i - 1) * (j - 1) * dp[i - 1][j - 1]) % mod
        if dp[i][j] < 0:
            dp[i][j] += mod


print(dp[c][d])

Submission status: Time Limit Exceeded

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

    return dp[C][D]

print(main())

Submission status: Time Limit Exceeded

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

d={}
d[(A,B)]=1
for i in range(A+1,C+1):
  d[(i,B)] = B*d[(i-1,B)] % 998244353
for j in range(B+1,D+1):
  d[(A,j)] = A*d[(A,j-1)] % 998244353
 
for i in range(A+1,C+1):
  for j in range(B+1,D+1):
    d[(i,j)]=(j*d[(i-1,j)]+i*d[(i,j-1)]-(i-1)*(j-1)*d[(i-1,j-1)]) % 998244353
    
print(d[(C,D)] % 998244353)

Submission status: Time Limit Exceeded

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

d={}
for i in range(A,C+1):
  d[(i,B)] = B**(i-A) % 998244353
for j in range(B,D+1):
  d[(A,j)] = A**(j-B) % 998244353
 
for i in range(A+1,C+1):
  for j in range(B+1,D+1):
    d[(i,j)]=(j*d[(i-1,j)]+i*d[(i,j-1)]-(i-1)*(j-1)*d[(i-1,j-1)]) % 998244353
    
print(d[(C,D)] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
A, B, C, D = map(int, input().split())
MOD = 998244353
dp = [[0]*(D+1) for i in range(C+1)]
for i in range(A, C+1):
    for j in range(B, D+1):
        if (i, j) == (A, B):
            dp[i][j] = 1
        else:
            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[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 4)

MOD = 998244353


def solve(A, B, C, D):
    cache = {}

    def numWays(rows, cols):
        if rows == A and cols == B:
            return 1

        key = rows * 4096 + cols
        if key not in cache:

            assert rows >= A and cols >= B
            ways = 0
            if rows > A:
                ways += cols * numWays(rows - 1, cols) % MOD
            if cols > B:
                ways += rows * numWays(rows, cols - 1) % MOD

            if rows > A and cols > B:
                ways -= (cols - 1) * (rows - 1) * numWays(rows - 1, cols - 1) % MOD
            cache[key] = ways % MOD
        return cache[key]

    return numWays(C, D) % MOD


A, B, C, D = [int(x) for x in input().split()]
print(solve(A, B, C, D))

Submission status: Time Limit Exceeded

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

d={}
for i in range(A,C+1):
  d[(i,B)] = B**(i-A)
for j in range(B,D+1):
  d[(A,j)] = A**(j-B)
 
for i in range(A+1,C+1):
  for j in range(B+1,D+1):
    d[(i,j)]=j*d[(i-1,j)]+i*d[(i,j-1)]-(i-1)*(j-1)*d[(i-1,j-1)]
    
print(d[(C,D)] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 5)

MOD = 998244353


def solve(A, B, C, D):
    cache = {}

    def numWays(rows, cols):
        if rows == A and cols == B:
            return 1

        key = rows * 4096 + cols
        if key not in cache:

            assert rows >= A and cols >= B
            ways = 0
            if rows > A:
                ways += cols * numWays(rows - 1, cols) % MOD
            if cols > B:
                ways += rows * numWays(rows, cols - 1) % MOD

            if rows > A and cols > B:
                ways -= (cols - 1) * (rows - 1) * numWays(rows - 1, cols - 1) % MOD
            cache[key] = ways % MOD
        return cache[key]

    return numWays(C, D) % MOD


A, B, C, D = [int(x) for x in input().split()]
print(solve(A, B, C, D))

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    mod = 998244353
    a, b, c, d = nm()
    n, m = c-a, d-b
    dp = [[0]*(m+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        dp[i+1][0] = dp[i][0] * b % mod
    for i in range(m):
        dp[0][i+1] = dp[0][i] * a % mod
    for i in range(1, n+1):
        for j in range(1, m+1):
            dp[i][j] = (dp[i][j-1] * (a + i) + dp[i-1][j] * (b + j) - dp[i-1][j-1] * (a + i - 1) * (b + j - 1)) % mod
    # if a < 10:
    #     prn(dp)
    print(dp[n][m])

    return

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

from functools import lru_cache

sys.setrecursionlimit(10 ** 5)

MOD = 998244353


def solve(A, B, C, D):
    @lru_cache(maxsize=None)
    def numWays(rows, cols):
        if rows == A and cols == B:
            return 1

        assert rows >= A and cols >= B
        ways = 0
        if rows > A:
            ways += cols * numWays(rows - 1, cols) % MOD
        if cols > B:
            ways += rows * numWays(rows, cols - 1) % MOD

        if rows > A and cols > B:
            ways -= (cols - 1) * (rows - 1) * numWays(rows - 1, cols - 1) % MOD
        return ways % MOD

    return numWays(C, D) % MOD


A, B, C, D = [int(x) for x in input().split()]
print(solve(A, B, C, D))