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 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
        ways = 0
        if rows > A:
            ways += cols * numWays(rows - 1, cols)
        if cols > B:
            ways += rows * numWays(rows, cols - 1)

        if rows > A and cols > B:
            ways -= (cols - 1) * (rows - 1) * numWays(rows - 1, cols - 1)
        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))

Submission status: Time Limit Exceeded

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

Submission status: Accepted

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

dp = [[0] * (D+1) for j 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:
            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

print(dp[C][D])

Submission status: Accepted

Solution code:
A,B,C,D = map(int, input().split())
MOD = 998244353
MAX_SIZE = 3010
dp = [[0] * MAX_SIZE for _ in range(MAX_SIZE)]

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

print(dp[C][D])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc046/tasks/agc046_b

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

Submission status: Accepted

Solution code:
import sys

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


def resolve():
    a, b, c, d = map(int, input().split())
    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 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)
            dp[i][j] %= mod

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

    return(dp[c][d])


    return None

if __name__ == '__main__':
    a,b,c,d = map(int,ipt().split())
    print(main(a,b,c,d))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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


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

    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 i == A and j == B:
                continue
            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[-1][-1])


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

p = 998244353

a,b,c,d = map(int,input().split())
dp = [[0 for _ in range(d+1)] for k in range(c+1)]
for i in range(a, c+1):
	for j in range(b, d+1):
		if i == a:
			if j == b:
				dp[i][j] = 1
			else:
				dp[i][j] = dp[i][j-1] * i % p
		elif j == b:
			dp[i][j] = dp[i-1][j] * j % p
		else:
			dp[i][j] = (dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)) % p

print(dp[c][d])

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    MOD = 998244353
    a, b, c, d = map(int, readline().split())
    h, w = c - a, d - b

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

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

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

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

    print(dp[c][d])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

P=998244353

dp = [[0 for j in range(3002)] for i in range(3002)]
dp[A][B] = 1

for row in range(A, C + 1):
    for col in range(B, D + 1):
        dp[row][col] += col * dp[row - 1][col] + row * dp[row][col - 1]
        dp[row][col] -= (row - 1) * (col - 1) * dp[row - 1][col - 1]
        dp[row][col] %= P

print(dp[C][D])

Submission status: Accepted

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

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

memo[A][B] = 1

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

Submission status: Accepted

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(1,c+1):
    for j in range(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: Accepted

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 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][j-1] * i + dp[i-1][j] * j - dp[i-1][j-1] * (i - 1) * (j - 1)) % mod
print(dp[C][D])

Submission status: Accepted

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

Solution code:
a,b,c,d=map(int,input().split())
def amari(a):
  return a % 998244353
X0=[[0]*d for i in range(c)]
X1=[[0]*d for i in range(c)]
X2=[[0]*d for i in range(c)]
X0[a-1][b-1]=1
for j in range(b,d):
 X0[a-1][j]=amari(X0[a-1][j-1]*(a-1))
 X1[a-1][j]=amari(X0[a-1][j-1]+X1[a-1][j-1]*(a-1))
 X2[a-1][j]=amari(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]=amari((X0[i-1][j-1]+X1[i-1][j-1]+X2[i-1][j-1])*j)
  if j>=2:
   X2[i][j-1]=amari(X1[i][j-2]+X2[i][j-2] *(i+1))
print(amari(X0[c-1][d-1]+X1[c-1][d-1]+X2[c-1][d-1]))

Submission status: Accepted

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) % mod2

    return dp[c][d] % mod2


print(main())

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

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

Submission status: Accepted

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
for i in range(A,C+1):
  for j in range(B,D+1):
    if i > A or j > B:
      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

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

Submission status: Accepted

Solution code:
A, B, C, D = (int(x) for x in input().split())
MOD = 998244353
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 i == A and j == B:
            continue
        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

print(dp[C][D])

Submission status: Accepted

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])%mod)

"""
print('dp1')
for x in dp1:
  print(x)
print('dp2')
for x in dp2:
  print(x)
"""

Submission status: Accepted

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

MOD = 998244353

dp = [[0]*3005 for i in range(3005)]
dp[c][d] = 1
for i in range(d,0,-1):
    dp[c][i-1] = dp[c][i]*c%MOD
for i in range(c-1,-1,-1):
    x = 0
    for j in range(d,-1,-1):
        dp[i][j] = (j*dp[i+1][j]+x) % MOD
        x += dp[i+1][j]
        x *= i
        x %= MOD


print(dp[a][b])

Submission status: Accepted

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
        if i-1 >= 0:
            dp1[i][j] = (j+1)*(dp1[i-1][j]+dp2[i-1][j])
            dp1[i][j] %= mod
        if j-1 >= 0:
            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: Accepted

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

#上と右

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



for h in range(A,C+1):
    for w in range(B,D+1):
        if h==A and w==B:
            dp[A][B]=1
            continue

        if h>A and w>B:
            x=dp[h][w-1]*h
            y=dp[h-1][w]*w
            z=dp[h-1][w-1]*(h-1)*(w-1)
            sub=x+y-z
            dp[h][w]=(sub)%p
        elif h==A:
            dp[h][w]=(dp[h][w-1]*h)%p
        else:
            dp[h][w]=(dp[h-1][w]*w)%p


print(dp[C][D])

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
MOD = 998244353
def main(A, B, C, D):
    I, J = C - A, D - B
    dp = [[0] * (I + 1) for _ in range(I + J + 1)]
    dp[0][0] = 1
    for k in range(1, I + J + 1):
        for i in range(min(I, k) + 1):
            j = k - i
            v = dp[k - 1][i - 1] * (j + B) % MOD if i >= 1 else 0
            h = dp[k - 1][i] * (i + A) % MOD
            d = dp[k - 2][i - 1] * (i + A - 1) * (j + B - 1) if k >= 2 and i >= 1 else 0
            dp[k][i] = (v + h - d) % MOD
    print(dp[I + J][I])

if __name__ == '__main__':
    input = sys.stdin.readline
    A, B, C, D = map(int, input().split())
    main(A, B, C, D)

Submission status: Accepted

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

MOD = 998244353

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

# |0|0|0|
# |0|1|0|
# |0|0|0|
dp[A][B] = 1

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

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

# |0|1|2|    |0|1|4|    |0|1|3|
# |0|1|1| -> |0|1|1| -> |0|1|1|
# |0|0|0|    |0|0|0|    |0|0|0|
for i in range(A + 1, C + 1):
    for j in range(B + 1, D + 1):
        dp[i][j] = (i * dp[i][j - 1]) % MOD
        dp[i][j] = (dp[i][j] + (j * dp[i - 1][j]) % MOD) % MOD
        dp[i][j] = (dp[i][j] - ((i - 1) * (j - 1) * dp[i - 1][j - 1]) % MOD) % MOD

print(dp[C][D])

Submission status: Accepted

Solution code:
#AGC046-B Extension
"""
https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2020-06-20agc046
「操作列の結果、完成図としてありうるものを数えよ」
という問題は、複数の操作後の完成図が同じ結果を取りうることを考慮し、
・完成図としてあり得るパターンの同値な言い換えを探す
・操作に制約を加えても同じ完成図を作成できることが一意になる
のどちらかを目指して、考察していく。

以下、問題の「縦を選んだ場合のマスの変化」は上ではなく下として考える。

ケース2の
2 1 3 4
について考える。
これは縦に1回と横に3回の追加を行うが、
実は縦の制御について、最も左端に存在する黒タイルについて場合分けをして良い。
w???
w???
b???
の盤面について考えた時、これは初手に縦の操作を選ぶことで達成できるが、
そうでないような操作で上図と同じような盤面になったとして、実は左下の位置が
黒になるような場合、？の位置もまた同じように決定されるので、そのような
操作は考慮しなくて良いことが分かる。

そのような操作とは、つまり、"縦方向の拡張を最速で行わなかった"ような操作である。
考察すべき2つめの条件、操作に制約を加えても同じ完成図を作成できることが一意になる
を達成することができた。

この時の?の組み合わせは、横拡張3回のうち、すべての拡張で3つを選べるので、
3*3通り
である。
次は、一番下の行で、初めて黒が出る位置を1つずつずらして考えていく。
w???
w???
wb??

この場合、右に1回横拡張を挟んで、すぐさま縦拡張,そのあと横拡張を2回行うので、
2*3*3

w???
w???
wwb?

2*2*3

w???
w???
wwwb

2*2*2

よって合計65通りとなる。

この操作をdpによって拡張する。
具体的には、
dp[i][j]:横幅iの時点で残りの縦幅がjの時、縦幅を利用する際の通し数
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
A,B,C,D = map(int,readline().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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod=998244353
a,b,c,d=map(int,input().split())
if a==c and b==d:
  print(1)
  exit()
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: Accepted

Solution code:
mod = 998244353

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

dp = [0] * (D + 1)
dp[B:D + 1] = [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: Accepted

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[-1][-1])

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 998244353

a, b, c, d = MAP()
dp0 = list2d(c+1, d+1, 0)
dp1 = list2d(c+1, d+1, 0)

dp1[a][b] = 1
for i in range(a, c+1):
    for j in range(b, d+1):
        dp0[i][j] += dp0[i-1][j] * j
        dp0[i][j] += dp1[i-1][j] * j
        dp1[i][j] += dp1[i][j-1] * i
        dp1[i][j] += dp0[i][j-1]
        dp0[i][j] %= MOD
        dp1[i][j] %= MOD
ans = (dp0[c][d] + dp1[c][d]) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 998244353

a, b, c, d = MAP()
dp = list2d(c+1, d+1, 0)

dp[a][b] = 1
for i in range(a, c+1):
    for j in range(b, d+1):
        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
ans = dp[c][d]
print(ans)

Submission status: Accepted

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

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, 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)
            dp[i][j] %= mod
print(dp[C][D])

Submission status: Accepted

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

mod = 998244353

dp = [[-1 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
def doubling(n, m, modulo=0):
    y = 1
    base = n
    tmp = m
    while tmp:
        if tmp % 2 == 1:
            y *= base
            if modulo > 0:
                y %= modulo
        base *= base
        if modulo > 0:
            base %= modulo
        tmp //= 2
    return y
for i in range(b, d):
    dp[a][i+1] = dp[a][i] * a
    dp[a][i+1] %= mod
for i in range(a, c):
    dp[i+1][b] = dp[i][b] * b
    dp[i+1][b] %= mod
for i in range(a+1, c+1):
    for j in range(b+1, d+1):
        dp[i][j] = j*dp[i-1][j] + i*dp[i][j-1] - (i-1)*(j-1)*dp[i-1][j-1]
        dp[i][j] %= mod

print(dp[c][d])

Submission status: Accepted

Solution code:
# 解説AC 復習しよう
a, b, c, d = map(int, input().split())
dp = [[0] * (d + 1) for i in range(c + 1)]
dp[a][b] = 1
mod = 998244353
for i in range(a, c + 1):
    for j in range(b, d + 1):
        if i > a or j > b:
            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: Accepted

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]) % mod)

Submission status: Accepted

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)]


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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

# dp[i][j]:i*jの盤面のときの盤面の組み合わせ
dp=[[0]*(d+1) for i in range(c+1)]

dp[a][b]=1
for i in range(a,c+1):
    for j in range(b,d+1):
        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: Accepted

Solution code:
mod = 998244353

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: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod =  998244353


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):
        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: Accepted

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

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

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

Submission status: Accepted

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
下から来たものと左から来たものを足す
その後、重なっているところを引く
"""
MOD = 998244353
A, B, C, D = lr()  # Cは縦
dp = [[0] * (D+1) for _ in range(C+1)]   # 1-indexed
dp[A][B] = 1
for i in range(A, C+1):
    for j in range(B, D+1):
        dp[i][j] += dp[i-1][j] * j + dp[i][j-1] * i
        dp[i][j] -= dp[i-1][j-1] * (i-1) * (j-1)
        dp[i][j] %= MOD

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

Submission status: Accepted

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) % MOD
    for i in range(b + 1, d + 1):
        dp[a][i] = (dp[a][i - 1] * a) % MOD
 
    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))) % MOD
            
 
    print(dp[-1][-1])
 
 
def main():
    n = getN()
    for _ in range(n):
        solve()
 
 
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin


def ni(): return int(ns())


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


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


A, B, C, D = na()

mod = 998244353

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

dp[A][B] = 1
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][b - 1] * A) % mod

for a in range(A + 1, C + 1):
    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

print(dp[C][D])

Submission status: Accepted

Solution code:
a,b,c,d=map(int,input().split());m=998244353;x=range(c+d);D=[[0]*6011for _ in[0]*6011];D[a][b]=1
for i in x:
 for j in x: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: Accepted

Solution code:
a,b,c,d=map(int,input().split());m=998244353;n=6011;x=range(c+d);D=[[0]*6011for _ in[0]*6011];D[a][b]=1
for i in x:
 for j in x: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])