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: Wrong Answer

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    a,b,c,d = map(int,ipt().split())
    dp = [[1]*(d+1) for i in range(c+1)]
    for i in range(b,d):
        dp[a][i+1] = dp[a][i]*a
    for i in range(a,c):
        dp[i+1][b] = dp[i][b]*b

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

    print(dp[c][d])


    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    a,b,c,d = map(int,ipt().split())
    dp = [[1]*(d+1) for i in range(c+1)]
    for i in range(b,d):
        dp[a][i+1] = dp[a][i]*a
    for i in range(a,c):
        dp[i+1][b] = dp[i][b]*b

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

    print(dp[c][d])


    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
a,b,c,d = map(int,input().split())
import numpy as n
dp=n.zeros((c+1,d+1),n.int32)
dp[a][b]=1
for i in range(a,c+1):
    for ii in range(b,d+1):
        if i>a:
            dp[i][ii]+= dp[i-1][ii] * ii
        if ii>b:
            dp[i][ii]+= dp[i][ii-1] * i
        if i>a and ii>b:
            dp[i][ii] -= dp[i-1][ii-1] * (i-1) * (ii-1)
print(dp[c][d])

Submission status: Wrong Answer

Solution code:
a,b,c,d=map(int,input().split())
def amari(a):
  return a % 998244353
import numpy as np
X=np.zeros((3, c, d),int)
X[0][a-1][b-1]=1
for j in range(b,d):
 X[0][a-1][j]=amari(X[0][a-1][j-1]*(a-1))
 X[1][a-1][j]=amari(X[0][a-1][j-1]+X[1][a-1][j-1]*(a-1))
 X[2][a-1][j]=amari(X[1][a-1][j-1]+X[2][a-1][j-1]*a)
for i in range(a,c):
 for j in range(b,d+1):
  X[1][i][j-1]=amari(X[0][i-1][j-1]+X[1][i-1][j-1]+X[2][i-1][j-1]*j)
  if j>=2:
   X[2][i][j-1]=amari(X[1][i][j-2]+X[2][i][j-2] *(i+1))
  else:
    X[2][i][j-1]=0
print(amari(X[0][c-1][d-1]+X[1][c-1][d-1]+X[2][c-1][d-1]))

Submission status: Wrong Answer

Solution code:
a,b,c,d=map(int,input().split())
import numpy as np
X0=np.zeros((c, d))
X1=np.zeros((c, d))
X2=np.zeros((c, d))
X0[a-1][b-1]=1
for j in range(b,d):
 X0[a-1][j]=(X0[a-1][j-1]*(a-1))% 998244353
 X1[a-1][j]=((X0[a-1][j-1]+X1[a-1][j-1]*(a-1)))% 998244353
 X2[a-1][j]=(X1[a-1][j-1]+(X2[a-1][j-1]*a))% 998244353
for i in range(a,c):
 for j in range(b,d+1):
  X1[i][j-1]=((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
  if j>=2:
   X2[i][j-1]=(X1[i][j-2]+X2[i][j-2] *(i+1)) % 998244353
  else:
    X2[i][j-1]=0
print((X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1])%998244353)

Submission status: Wrong Answer

Solution code:
a,b,c,d=map(int,input().split())
import numpy as np
X0=np.zeros((c, d),np.int32)
X1=np.zeros((c, d),np.int32)
X2=np.zeros((c, d),np.int32)
X0[a-1][b-1]=1
for j in range(b,d):
 X0[a-1][j]=(X0[a-1][j-1]*(a-1))% 998244353
 X1[a-1][j]=((X0[a-1][j-1]+X1[a-1][j-1]*(a-1)))% 998244353
 X2[a-1][j]=(X1[a-1][j-1]+(X2[a-1][j-1]*a))% 998244353
for i in range(a,c):
 for j in range(b,d+1):
  X1[i][j-1]=((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
  if j>=2:
   X2[i][j-1]=(X1[i][j-2]+X2[i][j-2] *(i+1)) % 998244353
print((X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1])%998244353)

Submission status: Wrong Answer

Solution code:
a,b,c,d=map(int,input().split())
import numpy as np
X0=np.zeros((c, d),np.int64)
X1=np.zeros((c, d),np.int64)
X2=np.zeros((c, d),np.int64)
X0[a-1][b-1]=1
for j in range(b,d):
 X0[a-1][j]=(X0[a-1][j-1]*(a-1))% 998244353
 X1[a-1][j]=((X0[a-1][j-1]+X1[a-1][j-1]*(a-1)))% 998244353
 X2[a-1][j]=(X1[a-1][j-1]+(X2[a-1][j-1]*a))% 998244353
for i in range(a,c):
 for j in range(b,d+1):
  X1[i][j-1]=((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j) % 998244353
  X2[i][j-1]=(X1[i][j-2]+X2[i][j-2] *(i+1)) % 998244353
print((X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1])%998244353)

Submission status: Wrong Answer

Solution code:
a,b,c,d=map(int,input().split())
import numpy as np
X0=np.zeros((c, d),np.int64)
X1=np.zeros((c, d),np.int64)
X2=np.zeros((c, d),np.int64)
X0[a-1][b-1]=1
for j in range(b,d):
 X0[a-1][j]=X0[a-1][j-1]*(a-1)
 X1[a-1][j]=(X0[a-1][j-1]+X1[a-1][j-1]*(a-1))
 X2[a-1][j]=X1[a-1][j-1]+(X2[a-1][j-1]*a)
for i in range(a,c):
 for j in range(b,d+1):
  X1[i][j-1]=((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j)
  X2[i][j-1]=X1[i][j-2]+(X2[i][j-2]*(i+1))
print((X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1])%998244353)

Submission status: Wrong Answer

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

dp1=[[0]*(d+1) for _ in range(c+1)]
dp2=[[0]*(d+1) for _ in range(c+1)]

for i in range(b+1,d+1):
  if a==1:
    dp1[a][i]=1 if i==b+1 else 0
    dp2[a][i]=0 if i==b+1 else 1
  else:
    dp1[a][i]=(pow(a-1,i-b-1,mod)*(i-b))%mod
    dp2[a][i]=(pow(a,i-b,mod)-dp1[a][i])%mod
for i in range(a+1,c+1):
  dp1[i][b]=pow(b,i-a,mod)
  dp2[i][b]=0
dp2[a][b]=1
for i in range(a+1,c+1):
  for j in range(b+1,d+1):
    dp1[i][j]=(j*(dp1[i-1][j]+dp2[i-1][j]))%mod
    dp2[i][j]=(dp1[i][j-1]+dp2[i][j-1]*i)%mod
print(dp1[c][d]+dp2[c][d])
"""
print('dp1')
for x in dp1:
  print(x)
print('dp2')
for x in dp2:
  print(x)
"""

Submission status: Wrong Answer

Solution code:
a,b,c,d=map(int,input().split())
mod=998244353
import sys
sys.setrecursionlimit(10**7)

dp1=[[0]*(d+1) for _ in range(c+1)]
dp2=[[0]*(d+1) for _ in range(c+1)]

for i in range(b+1,d+1):
  if a==1:
    dp1[a][i]=1 if i==b+1 else 0
    dp2[a][i]=0 if i==b+1 else 1
  else:
    dp1[a][i]=(pow(a-1,i-b-1,mod)*(i-b))%mod
    dp2[a][i]=(pow(a,i-b,mod)-dp1[a][i])%mod
for i in range(a+1,c+1):
  dp1[i][b]=pow(b,i-a,mod)
  dp2[i][b]=0
dp2[a][b]=1
for i in range(a+1,c+1):
  for j in range(b+1,d+1):
    dp1[i][j]=(j*(dp1[i-1][j]+dp2[i-1][j]))%mod
    dp2[i][j]=(dp1[i][j-1]+dp2[i][j-1]*i)%mod
print(dp1[c][d]+dp2[c][d])
"""
print('dp1')
for x in dp1:
  print(x)
print('dp2')
for x in dp2:
  print(x)
"""

Submission status: Wrong Answer

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

dp1 = [[0 for j in range(d)] for i in range(c)] # 一番下の行に黒一つは下に追加で得られた場合に限って良い (下に追加する前の盤を初期状態から作れるので)
dp2 = [[0 for j in range(d)] for i in range(c)] # その状態が右に追加することでしか得られない場合 (一番下の行に黒複数 or a==c)
dp2[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
        dp1[i][j] = (j+1)*(dp1[i-1][j]+dp2[i-1][j])
        dp1[i][j] %= mod
        dp2[i][j] = dp1[i][j-1] + (i+1)*dp2[i][j-1]
        dp2[i][j] %= mod

ans = (dp1[c-1][d-1] + dp2[c-1][d-1]) % mod
print(ans)

Submission status: Wrong Answer

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

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, D+1):
    for i in range(A, C+1):
        dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod
        if j < D:
            dp[i][j+1] = (dp[i][j+1] + dp[i][j] * i) % mod
print(dp[C][D])

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

MOD=998244353

#dp[i][j]たてにi回、横にj回追加したときの数
DP=[[0]*(D-B+1) for _ in range(C-A+1)]
DP[0][0]=1

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

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

print(DP)
print(DP[-1][-1])

Submission status: Wrong Answer

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

MOD=998244353

#dp[i][j]たてにi回、横にj回追加したときの数
DP=[[0]*(D-B+1) for _ in range(C-A+1)]
DP[0][0]=1

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

print(DP)

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

print(DP[-1][-1])

Submission status: Wrong Answer

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

dp0 = [0] * (c-a+1)
dp1 = [1]

for i in range(c-a):
    dp1.append(dp1[-1] * b % mod)

for j in range(1, d-b+1):
    new_dp0 = [(dp0[0] * a + dp1[0]) % mod]
    new_dp1 = [dp1[0] * (a-1) % mod]
    for i in range(1, c-a+1):
        new_dp0.append((dp0[i] * (a+i) + dp1[i]) % mod)
        new_dp1.append((new_dp0[-2] + new_dp1[-1]) * (b+j) % mod)

    dp0 = new_dp0
    dp1 = new_dp1

print(dp0[-1] + dp1[-1])

Submission status: Wrong Answer

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

dp0 = [0] * (c-a+1)
dp1 = [1]

for i in range(c-a):
    dp1.append(dp1[-1] * b % mod)

i = [dp0[i] + dp1[i] for i in range(len(dp0))]
print(i)

for j in range(1, d-b+1):
    new_dp0 = [(dp0[0] * a + dp1[0]) % mod]
    new_dp1 = [dp1[0] * (a-1) % mod]
    for i in range(1, c-a+1):
        new_dp0.append((dp0[i] * (a+i) + dp1[i]) % mod)
        new_dp1.append((new_dp0[-2] + new_dp1[-1]) * (b+j) % mod)

    dp0 = new_dp0
    dp1 = new_dp1

    i = [dp0[i] + dp1[i] for i in range(len(dp0))]
    print(i)

print(dp0[-1] + dp1[-1])

Submission status: Wrong Answer

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

dp = [[[0, 1]]]

for i in range(c-a):
    dp[0].append([0, dp[0][-1][1] * b % mod])

for j in range(d-b):
    dp.append([[(dp[-1][0][0] * a + dp[-1][0][1]) % mod, dp[-1][0][1] * (a-1) % mod]])
    for i in range(c-a):
        dp[-1].append([(dp[-2][i+1][0] * (a+i+1) + dp[-2][i+1][1]) % mod, sum(dp[-1][-1]) * (b+j+1) % mod])

print(sum(dp[d-b][c-a]))

Submission status: Wrong Answer

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

x = c-a
y = d-b
dp = [[0]*(y+2) for i in range(x+1)]
dp[0][0] = 1

for i in range(x+1):
    for j in range(y+1):
        dp[i][j] += (dp[i][j-1]*(i+a)+dp[i-1][j]*(j+b)-dp[i-1][j-1]*(i+a-1)*(j+b-1))%mod
        dp[i][j]%=mod
print(dp[-1][-2]%mod)

Submission status: Wrong Answer

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


def main():
    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)


if __name__ == '__main_':
    main()

Submission status: Wrong Answer

Solution code:
import sys
# from collections import defaultdict, deque
import math

# import copy
# from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 998244353

def solve():
    a, b, c, d = getList()
    dp = [[1 for i in range(d + 1)] for j in range(c + 1)]

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

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

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


def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

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

#ここまでのパテーン
#dp[y][x]=dp[y][x-1]*y +dp[y-1][x]*x

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

if a==c and b==d:
    print(0)
    exit()

if a==c:
    print((a**(d-b))%mod)
    exit()
if b==d:
    print((b**(c-a))%mod)
    exit()


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

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

Submission status: Wrong Answer

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

#ここまでのパテーン
#dp[y][x]=dp[y][x-1]*y +dp[y-1][x]*x

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

for y in range(a-1,c):
    for x in range(b-1,d):
        
        dp[y][x]+=max(dp[y][x-1]*(y+1) +dp[y-1][x]*(x+1)-dp[y-1][x-1]*x*y,0)
        dp[y][x]=dp[y][x]%mod
        #print(y,x,dp[y][x])
#pri(dp)
print(dp[-1][-1]%mod)

Submission status: Wrong Answer

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

def pri(x):
    x=x[::-1]
    for item in x:
        print(item)

#ここまでのパテーン
#dp[y][x]=dp[y][x-1]*y +dp[y-1][x]*x

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

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

Submission status: Wrong Answer

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

def pri(x):
    x=x[::-1]
    for item in x:
        print(item)

#ここまでのパテーン
#dp[y][x]=dp[y][x-1]*y +dp[y-1][x]*x

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

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

Submission status: Wrong Answer

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

DP = [[0]*3001]*3001
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: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=998244353
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

a,b,c,d=map(int,input().split())
dp=[[0]*(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
for j in range(b+1,d+1):
    dp[a][j]=dp[a][j-1]*a
# print(dp)

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)
        dp[i][j]%=mod

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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    mod = 998244353
    A, B, C, D = map(int, input().split())
    dp = [[1] * (D+1) for _ in range(C+1)]
    for i, w in enumerate(range(B+1, D+1)):
        dp[A][w] = A ** (i+1)
    for i, h in enumerate(range(A+1, C+1)):
        dp[h][B] = B ** (i+1)
    for h in range(A+1, C+1):
        for w in range(B+1, D+1):
            dp[h][w] = (dp[h-1][w]*w%mod + dp[h][w-1]*h%mod - dp[h-1][w-1]*(h-1)*(w-1)%mod) % mod
    print(dp[C][D])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    mod = 998244353
    A, B, C, D = map(int, input().split())
    dp = [[1] * (D+1) for _ in range(C+1)]
    for i, w in enumerate(range(B+1, D+1)):
        dp[A][w] = A ** (i+1)
    for i, h in enumerate(range(A+1, C+1)):
        dp[h][B] = B ** (i+1)
    for h in range(A+1, C+1):
        for w in range(B+1, D+1):
            dp[h][w] = dp[h-1][w]*w + dp[h][w-1]*h - dp[h-1][w-1]*(h-1)*(w-1)
    print(dp[C][D])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def fer(n, r, p):
    # calculate n_C_k mod p
    # a,pが互いに素のとき a ^ (p-2) = a ^ -1 (mod p)
    # これを使って分母のmodを高速に計算できる
    x, y = 1, 1
    for i in range(r):
        x *= (n - i)
        x %= p
        y *= (i + 1)
        y %= p
    # x -> n * (n-1) * ... * (n-r+1)
    # y -> 1 * 2 * ... * r
    return x * pow(y, p - 2, p) % p


def main():
    import sys
    sys.setrecursionlimit(1000000000)
    a, b, c, d = map(int, input().split())
    mod = 998244353
    p = c * d - 1
    q = (c - a) + (d - b)
    ans = fer(p, q, mod)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

powA=1
for i in range(A+1,C+1):
  powA*=B
  powA%=MOD
  dp[i][B]=powA
  
powB=1
for i in range(B+1,D+1):
  powB*=A
  powB%=MOD
  dp[A][i]=powB
#print(dp)

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

Submission status: Wrong Answer

Solution code:
def main():
    MOD = 998244353
    A, B, H, W = map(int, input().split())

    cumsum = [0] * (H + 1)
    for h in range(A, H + 1):
        cumsum[h] = 1

    for c in range(B + 1, W + 1):
        next_cumsum = [0] * (H + 1)
        for h in range(A, H + 1):
            next_cumsum[h] = (next_cumsum[h] + next_cumsum[h - 1] + cumsum[h] * h) % MOD
        cumsum = next_cumsum

    print(cumsum[H])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

MOD = 998244353

dp1 = [[0]*3000 for _ in range(3000)]
dp2 = [[0]*3000 for _ in range(3000)]
dp3 = [[0]*3000 for _ in range(3000)]

dp1[0][0] = 1

for i in range(d-b+1):
    for j in range(c-a+1):
        if i-1>=0:
            dp1[i][j]=dp1[i-1][j]*a
            if j-1>=0:
                dp2[i][j]=dp1[i-1][j]*j+dp3[i-1][j]*j+dp2[i-1][j]*(a+j)#+dp2[i][j-1]*(b+i-1)
        if j-1>=0:
            dp1[i][j]=dp1[i][j-1]*b
            if i-1>=0:
                dp3[i][j]=dp1[i][j-1]*i+dp2[i][j-1]*i+dp3[i][j-1]*(b+i)#+dp3[i-1][j]*(a+j-1)
        dp1[i][j]%=MOD
        dp2[i][j]%=MOD
        dp3[i][j]%=MOD

print((dp1[d-b][c-a]+dp2[d-b][c-a]+dp3[d-b][c-a])%MOD)

Submission status: Wrong Answer

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)) % MOD
    
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

a,b,c,d = list(map(int,input().split()))
p,q = c-a+1, d-b+1

MOD = 998244353

dp = [[0 for _ in range(q)] for _ in range(p)]
dp[0][0] = 1

# print(p,q)

for i in range(1, p):
    dp[i][0] = dp[i-1][0]*b

for j in range(1, q):
    dp[0][j] = dp[0][j-1]*a

# print(dp)

for i in range(1,p):
    for j in range(1,q):
        # print((a+i), dp[i][j-1], dp[i-1][j])
        dp[i][j] = (a+i)*dp[i][j-1] + dp[i-1][j]
        dp[i][j] = dp[i][j]%MOD
# print(dp)

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

Submission status: Wrong Answer

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

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

ans = 0
dx = d - b
dy = c - a
import itertools
A = [int(x) for x in range(a, c + 1)]
B = list(itertools.combinations_with_replacement(A, dx))
for C in B:
    s = 1
    for D in C:
        s *= D
        s %= mod
    ans += s
print(ans)

Submission status: Wrong Answer

Solution code:
a, b, c, d = map(int, input().split())
m = c - a + 1
n = d - b + 1
n_list = [0]*n
m_list = [0]*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)

Submission status: Wrong Answer

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

MOD = 998244353

dp1 = [[0]*3000 for _ in range(3000)]
dp2 = [[0]*3000 for _ in range(3000)]
dp3 = [[0]*3000 for _ in range(3000)]

dp1[0][0] = 1

for i in range(d-b+1):
    for j in range(c-a+1):
        if i-1>=0:
            dp1[i][j]=dp1[i-1][j]*a
            if j-1>=0:
                dp2[i][j]=dp1[i-1][j]+dp3[i-1][j]+dp2[i-1][j]*(a+j)+dp2[i][j-1]*(b+i-1)
        if j-1>=0:
            dp1[i][j]=dp1[i][j-1]*b
            if i-1>=0:
                dp3[i][j]=dp1[i][j-1]+dp2[i][j-1]+dp3[i][j-1]*(b+i)+dp3[i-1][j]*(a+j-1)
        dp1[i][j]%=MOD
        dp2[i][j]%=MOD
        dp3[i][j]%=MOD

print((dp1[d-b][c-a]+dp2[d-b][c-a]+dp3[d-b][c-a])%MOD)

Submission status: Wrong Answer

Solution code:
import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]

def ldec(A, d=1): return map(lambda x: x - d, A)

sys.setrecursionlimit(5000)

A, B, C, D = nn()

memo_f = {}
memo_g = {}
mod = 998244353

def f(x, y):
    if x == A: return pow(A, y - B, mod)
    if y == B: return pow(B, x - A, mod)
    if (x, y) in memo_f:
        return memo_f[(x, y)]

    s = (f(x-1, y) * y) % mod
    t = (f(x, y-1) * x) % mod
    u = (g(x-1, y) * (y-1)) % mod
    memo_f[(x, y)] = (s + t - u) % mod
    return (s + t - u) % mod

def g(x, y):
    if x == A: return pow(A, y - B, mod)
    if y == B: return pow(B, x - A, mod)

    s = (f(x, y-1) * x) % mod
    t = (g(x-1, y) * (y-1)) % mod
    return (s + t) % mod

print(f(C, D))

Submission status: Wrong Answer

Solution code:
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
a,b,c,d=map(int,input().split())
mod=998244353


dp=[[0]*3005 for _ in range(3005)]
for i in range(a+1):
    for j in range(b+1):
        dp[i][j]=1
#print(dp)

for i in range(3003-b):
    dp[a][b+i+1]=((dp[a][b+i])*a)%mod
for j in range(3003-a):
    dp[a+1+j][b]=((dp[a+j][b]*b))%mod

    
for i in range(a,3003-a):
    for j in range(b,3003-b):
        dp[i+1][j+1]=(dp[i][j+1]*(j+1))%mod+(dp[i+1][j]*(i+1))%mod-(i*j)

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

Submission status: Wrong Answer

Solution code:
MOD = 998244353
A, B, C, D = map(int, input().split())
H = C-A+1
W = D-B+1
dp = [[0]*(W+1) for _ in range(H+1)]
dp[1][1] = 1
mods = [[0]*(W+1) for _ in range(H+1)]
for i in range(H):
    for j in range(W):
        if i==0 and j==0: continue
        # if i==0 or j==0:
        #     dp[i+1][j+1] = dp[i+1][j] * (A+i) + dp[i][j+1] * (B+j)
        # else:
        #     dp[i+1][j+1] = max(dp[i+1][j] * (A+i) + dp[i][j+1] , dp[i+1][j] + dp[i][j+1] * (B+j))
        #     # dp[i+1][j+1] = dp[i+1][j] * (A+i) + dp[i][j+1] * (B+j) - nCr(max(dp[i+1][j],dp[i][j+1]), min(dp[i+1][j],dp[i][j+1]))
        #     # print(nCr(max(dp[i+1][j],dp[i][j+1]), min(dp[i+1][j],dp[i][j+1])))
        if mods[i+1][j] > mods[i][j+1]:
            dp[i+1][j+1] = dp[i+1][j] * (A+i) + dp[i][j+1]
            mods[i+1][j+1] = mods[i+1][j]
        elif mods[i+1][j] < mods[i][j+1]:
            dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] * (B+j)
            mods[i+1][j+1] = mods[i][j+1]
        else:
            dp[i+1][j+1] = max(dp[i+1][j] * (A+i) + dp[i][j+1] , dp[i+1][j] + dp[i][j+1] * (B+j))
            mods[i+1][j+1] = max(mods[i+1][j], mods[i][j+1])
        div, mod = divmod(dp[i+1][j+1], MOD)
        dp[i+1][j+1] = mod
        mods[i+1][j+1] += div
        # dp[i+1][j+1] = max(dp[i+1][j] * (A+i) + dp[i][j+1] , dp[i+1][j] + dp[i][j+1] * (B+j))
        # dp[i+1][j+1] %= MOD
# print(dp)
# print(dp[H][W])
print(dp[H][W] % MOD)

Submission status: Wrong Answer

Solution code:
MOD = 998244353
A, B, C, D = map(int, input().split())
H = C-A+1
W = D-B+1
dp = [[0]*(W+1) for _ in range(H+1)]
dp[1][1] = 1
mods = [[0]*(W+1) for _ in range(H+1)]
for i in range(H):
    for j in range(W):
        if i==0 and j==0: continue
        # if i==0 or j==0:
        #     dp[i+1][j+1] = dp[i+1][j] * (A+i) + dp[i][j+1] * (B+j)
        # else:
        #     dp[i+1][j+1] = max(dp[i+1][j] * (A+i) + dp[i][j+1] , dp[i+1][j] + dp[i][j+1] * (B+j))
        #     # dp[i+1][j+1] = dp[i+1][j] * (A+i) + dp[i][j+1] * (B+j) - nCr(max(dp[i+1][j],dp[i][j+1]), min(dp[i+1][j],dp[i][j+1]))
        #     # print(nCr(max(dp[i+1][j],dp[i][j+1]), min(dp[i+1][j],dp[i][j+1])))
        # if mods[i+1][j] > mods[i][j+1]:
        #     dp[i+1][j+1] = dp[i+1][j] * (A+i) + dp[i][j+1]
        #     mods[i+1][j+1] = mods[i+1][j]
        # elif mods[i+1][j] < mods[i][j+1]:
        #     dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] * (B+j)
        #     mods[i+1][j+1] = mods[i][j+1]
        # else:
        #     dp[i+1][j+1] = max(dp[i+1][j] * (A+i) + dp[i][j+1] , dp[i+1][j] + dp[i][j+1] * (B+j))
        #     mods[i+1][j+1] = max(mods[i+1][j], mods[i][j+1])
        # div, mod = divmod(dp[i+1][j+1], MOD)
        # dp[i+1][j+1] = mod
        # mods[i+1][j+1] += div
        dp[i+1][j+1] = max(dp[i+1][j] * (A+i) + dp[i][j+1] , dp[i+1][j] + dp[i][j+1] * (B+j))
        dp[i+1][j+1] %= MOD
# print(dp)
# print(dp[H][W])
print(dp[H][W] % MOD)

Submission status: Wrong Answer

Solution code:
MOD = 998244353
A, B, C, D = map(int, input().split())
H = C-A+1
W = D-B+1
dp = [[0]*(W+1) for _ in range(H+1)]
dp[1][1] = 1
mods = [[0]*(W+1) for _ in range(H+1)]
for i in range(H):
    for j in range(W):
        if i==0 and j==0: continue
        # if i==0 or j==0:
        #     dp[i+1][j+1] = dp[i+1][j] * (A+i) + dp[i][j+1] * (B+j)
        # else:
        #     dp[i+1][j+1] = max(dp[i+1][j] * (A+i) + dp[i][j+1] , dp[i+1][j] + dp[i][j+1] * (B+j))
        #     # dp[i+1][j+1] = dp[i+1][j] * (A+i) + dp[i][j+1] * (B+j) - nCr(max(dp[i+1][j],dp[i][j+1]), min(dp[i+1][j],dp[i][j+1]))
        #     # print(nCr(max(dp[i+1][j],dp[i][j+1]), min(dp[i+1][j],dp[i][j+1])))
        # if mods[i+1][j] > mods[i][j+1]:
        #     dp[i+1][j+1] = dp[i+1][j] * (A+i) + dp[i][j+1]
        #     mods[i+1][j+1] = mods[i+1][j]
        # elif mods[i+1][j] < mods[i][j+1]:
        #     dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] * (B+j)
        #     mods[i+1][j+1] = mods[i][j+1]
        # else:
        #     dp[i+1][j+1] = max(dp[i+1][j] * (A+i) + dp[i][j+1] , dp[i+1][j] + dp[i][j+1] * (B+j))
        #     mods[i+1][j+1] = max(mods[i+1][j], mods[i][j+1])
        # div, mod = divmod(dp[i+1][j+1], MOD)
        # dp[i+1][j+1] = mod
        # mods[i+1][j+1] += div
        dp[i+1][j+1] = max(dp[i+1][j] * (A+i) + dp[i][j+1] , dp[i+1][j] + dp[i][j+1] * (B+j))
        # dp[i+1][j+1] %= MOD
# print(dp)
# print(dp[H][W])
print(dp[H][W] % MOD)

Submission status: Wrong Answer

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

# n回操作
n = c + d - a - b

dp = [1]

for i in range(n):
    new = [dp[0]*b % mod]
    for j in range(i):
        if i-j >= j+1:
            new.append(((a+i-j)*dp[j] + (b+j+1)*dp[j+1] - (dp[j]-j)*(a+i-j-1)) % mod)
        else:
            new.append(((a+i-j)*dp[j] + (b+j+1)*dp[j+1] - (dp[j+1]-(i-j-1))*(b+j)) % mod)
    new.append(dp[i]*a % mod)
    dp = new

print(dp[n - c + a])