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

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

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

x, y = A, B
dp[x][y] = 1

for i in range(x, C+1):
    for j in range(y, D+1):
        if i == x and j == y:
            continue

        if i > x:
            dp[i][j] += dp[i-1][j] * j
        if j > y:
            dp[i][j] += dp[i][j-1] * i

        if i > x and j > y:
            dp[i][j] -= (i-1) * (j-1) * dp[i-1][j-1]

        dp[i][j] %= mod

print(dp[C][D])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

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


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

dp1[a][b] = 1

#print(dp1)
#print(dp2)
MOD = 998244353
for i in range(a,c+1):
    for j in range(b,d+1):
        if i != c:
            dp1[i+1][j] += j*dp1[i][j]
            dp1[i+1][j] += dp2[i][j]
            dp1[i+1][j] %= MOD
        if j != d:
            dp2[i][j+1] += i*dp2[i][j]
            dp2[i][j+1] += i*dp1[i][j]
            dp2[i][j+1] %= MOD
            
#print(dp1)
#print(dp2)

print((dp1[c][d]+dp2[c][d])%MOD)

Submission status: Accepted

Solution code:
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:
            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:
MOD = 998244353

def fastExponentiation(a,b,N): # Calculates a^b mod N in log b time
    ans = 1
    bDiv2 = b
    aPow2 = a
    while bDiv2 > 0:
        if bDiv2 % 2 != 0:
            ans *= aPow2
            ans %= N
        bDiv2 //= 2
        aPow2 = aPow2 * aPow2
        aPow2 %= N
    return ans

a,b,c,d = map(int,input().split())
DP = []
for i in range(c-a+1):
    DP.append([])
    for j in range(d-b+1):
        DP[i].append(0)

for i in range(c-a+1):
    partialSum = 0
    if i == 0:
        DP[i][0] = 1
        continue
    for j in range(d-b+1):
        if j == 0:
            DP[i][j] = (DP[i-1][j] * b) % MOD
        else:
            partialSum += DP[i-1][j-1]
            partialSum *= (a + i - 1)
            partialSum %= MOD
            DP[i][j] = (DP[i-1][j] * (j + b) + partialSum) % MOD

ans = 0
for j in range(d-b+1):
    ans = ans + DP[c-a][j] * fastExponentiation(c,d-b-j,MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

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

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

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

print(DP[C][D]%mod)

Submission status: Accepted

Solution code:
MOD = 998244353


def solve(A, B, C, D):
    numWays = [[None for c in range(D + 1)] for r in range(C + 1)]

    numWays[A][B] = 1

    for rows in range(A, C + 1):
        for cols in range(B, D + 1):
            if rows == A and cols == B:
                continue
            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
            numWays[rows][cols] = 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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 998244353
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    A,B,C,D = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    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
            #print(i,j)
            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])





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

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 i == A and j == B:
            continue
        dp[i][j] = (dp[i-1][j]*j)%mod + (dp[i][j-1]*i)%mod\
                     - (dp[i-1][j-1]*(i-1)*(j-1))%mod
        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 for _ in range(c)]
dp[a-1][b-1] = 1

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

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
from functools import lru_cache

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

def main(A, B, C, D):
    dp = np.zeros((C + 1, D + 1), np.int64)
    dp[C, D] = 1
    for d in range(D, 0, -1):
        dp[C, d - 1] = dp[C, d] * C % MOD
    for c in range(C - 1, -1, -1):
        x = 0
        for d in range(D, -1, -1):
            dp[c, d] = (d * dp[c + 1, d] + x) % MOD
            x += dp[c + 1, d]
            x *= c
            x %= MOD
    return dp[A, B]

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    signature = (i8, i8, i8, i8)

    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()

from my_module import main

A, B, C, D = map(int, read().split())
print(main(A, B, C, D))

Submission status: Accepted

Solution code:
"""

ありうるものは？
差の分だけ塗れる

ｄｐ？
dp[i][j] = dp[i-1][j] * j + dp[i][j-1] * i
i,jの中に 丁度i-A,j-B個ある置き方は全部できる

dp[i][j] = dp[i-1][j] * j + dp[i][j-1] * i - dp[i-1][j-1] * (i-1) * (j-1)

i,j置いた時に
i+j個の黒が入っているはず
→ i-1,jにi+j-1こはいってる * j + i-1,jにi+j-1こはいってる* i - どっちも満たしてる

"""

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

Submission status: Accepted

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

P = 998244353
def mod_prod(a,b):
    return (a % P) * (b % P) % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n >> 1
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret

def solve():
    A, B, C, D = map(int, readline().split())

    dp = [[0] * D for i in range(C)]

    dp[A - 1][B - 1] = 1

    for i in range(C):
        for j in range(D):
            if i >= A or j >= B:
                dp[i][j] = (
                    (dp[i - 1][j] * (j + 1) if i > 0 else 0)
                    + (dp[i][j - 1] * (i + 1) if j > 0 else 0)
                    - (dp[i - 1][j - 1] * i * j if i > 0 and j > 0 else 0)
                   ) % P
    print(dp[-1][-1])

solve()

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np


def main():
	a,b,c,d=MI()
	dp=[[0]*(d+1) for _ in range(c+1)]
	dp[a][b]=1

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

	print(dp[c][d])
















if __name__ == "__main__":
	main()

Submission status: Accepted

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

for i in range(C):
    for j in range(D):
        if i!=A-1 or j!=B-1:
            val1 = dp[i-1][j]*(j+1)
            if i==0:
                val1 = 0
            val2 = dp[i][j-1]*(i+1)
            if j==0:
                val2 = 0
            val3 = 0
            if val1*val2!=0:
                val3 = i*j
            dp[i][j] = (val1+val2 - val3*dp[i-1][j-1])%MOD
            #dp[i][j] = (dp[i-1][j]*(j+1) + dp[i][j-1]*(i+1) - i*j)%MOD
# print(dp)
print(dp[C-1][D-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 998244353
INF = 10 ** 9

def main():
    A,B,C,D = map(int,input().split())
    dp = [[0]*(1+D) for _ 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
            dp[i + 1][j + 1] = (i + 1)*dp[i + 1][j] + (j + 1)*dp[i][j + 1] - dp[i][j] * i*j
            dp[i + 1][j + 1] %= MOD
    print(dp[C][D])
if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

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

Submission status: Accepted

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

A[a][b] = 1

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

Submission status: Accepted

Solution code:
P = 998244353
A, B, C, D = map(int, input().split())
X = [[0] * 3001 for _ in range(3001)]
for a in range(3001):
    for b in range(3001):
        if a < A or b < B: continue
        if a == A and b == B:
            X[a][b] = 1
        elif a == A:
            X[a][b] = X[a][b-1] * a % P
        elif b == B:
            X[a][b] = X[a-1][b] * b % P
        else:
            X[a][b] = (X[a-1][b] * b + X[a][b-1] * a - X[a-1][b-1] * (a-1) * (b-1)) % P

print(X[C][D])

Submission status: Accepted

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

Submission status: Accepted

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

Solution code:
def rec(i, j):
    if memo[i][j]!=-1:
        return memo[i][j]
        
    if i==A and j==B:
        res = 1
    elif i==A:
        res = A*rec(i, j-1)%MOD
    elif j==B:
        res = B*rec(i-1, j)%MOD
    else:
        #この式だとなんかダメ
        #res = ((i-1)*(j-1)*rec(i-1, j-1)+rec(i-1, j)+rec(i, j-1))%MOD
        res = (i*rec(i, j-1)+j*rec(i-1, j)-(i-1)*(j-1)*rec(i-1, j-1))%MOD

    memo[i][j] = res
    return res

A, B, C, D = map(int, input().split())
MOD = 998244353
memo = [[-1]*(D+1) for _ in range(C+1)]
print(rec(C, D))

Submission status: Runtime Error

Solution code:
import numpy as np

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: Runtime Error

Solution code:
import numpy as np

p = 998244353

a,b,c,d = map(int,input().split())
dp = np.zeros((c+1, d+1), dtype=np.int64)
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: Runtime Error

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

#上と右

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

dp[A+1][B]=B
dp[A][B+1]=A

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: Runtime Error

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

#上と右

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

dp[A+1][B]=B
dp[A][B+1]=A
print(dp)
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: Runtime Error

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の時、縦幅を利用する際の通し数
"""
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: Runtime Error

Solution code:
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 998244353 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

signed main(){
    ll A,B,C,D;cin>>A>>B>>C>>D;
    //i番目はi個の列or行を選んでる
    vector<map<pair<ll,ll>,ll>> dp((D+C)-(B+A)+1);
    dp[0][MP(A,B)]=1;
    //dp[1][MP(A+1,B)]=B;
    //dp[1][MP(A,B+1)]=A;
    REP(i,(D+C)-(B+A)){
        for(auto j=dp[i].begin();j!=dp[i].end();j++){
            ll a,b;a=j->F.F;b=j->F.S;
            dp[i+1][MP(a,b+1)]+=(dp[i][MP(a,b)]*(a));
            dp[i+1][MP(a,b+1)]%=MOD;
            dp[i+1][MP(a+1,b)]+=(dp[i][MP(a,b)]*(b));
            dp[i+1][MP(a+1,b)]%=MOD;
        }
        if(i==0)continue;
        for(auto j=dp[i+1].begin();j!=dp[i+1].end();j++){
            ll a,b;a=j->F.F;b=j->F.S;
            if(a!=A and b!=B){
                dp[i+1][MP(a,b)]+=MOD;
                dp[i+1][MP(a,b)]-=(dp[i-1][MP(a-1,b-1)]*(a-1)*(b-1)%MOD);
                dp[i+1][MP(a,b)]%=MOD;
            }
        }
    }
    cout<<dp[(D+C)-(B+A)][MP(C,D)]%MOD<<endl; 
    #if 0
    REP(i,(D+C)-(B+A)+1){
        for(auto j=dp[i].begin();j!=dp[i].end();j++){
            ll a,b;a=j->F.F;b=j->F.S;
            cout << a << " " << b << " " << j->S << endl;
        }
    }
    #endif
}

Submission status: Runtime Error

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: Runtime Error

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

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

Solution code:
	#include<bits/stdc++.h>
	using namespace std;
	using ll = long long;
	#define forn(i,n) for(int i = 0; i< n;++i)
	int INF = 1e9 + 7;
	ll MOD = 998244353;


	int main(){
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
		int a,b,c,d;
		cin >> a >> b >> c >> d;

		vector<vector<ll>> dp(c+10,vector<ll>(d+10,0));
		
		for(int i = a; i <= c; ++i){
			for(int j = b; j <= d; ++j){
				if(i == a && 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);
				//dp[i][j] %= MOD;
				dp[i][j] = (MOD + dp[i][j] % MOD) % MOD;
			}
		}
		cout << dp[c][d] << endl;
				
	}

Submission status: Runtime Error

Solution code:
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

signed main(){
    ll A,B,C,D;cin>>A>>B>>C>>D;
    //i番目はi個の列or行を選んでる
    vector<map<pair<ll,ll>,ll>> dp((D+C)-(B+A)+1);
    dp[0][MP(A,B)]=1;
    //dp[1][MP(A+1,B)]=B;
    //dp[1][MP(A,B+1)]=A;
    REP(i,(D+C)-(B+A)){
        for(auto j=dp[i].begin();j!=dp[i].end();j++){
            ll a,b;a=j->F.F;b=j->F.S;
            dp[i+1][MP(a,b+1)]+=(dp[i][MP(a,b)]*(a));
            dp[i+1][MP(a+1,b)]+=(dp[i][MP(a,b)]*(b));
            //cout << a << " " << b << " " << j->S << endl;
        }
        #if 1
        if(i==0)continue;
        for(auto j=dp[i+1].begin();j!=dp[i+1].end();j++){
            ll a,b;a=j->F.F;b=j->F.S;
            if(a!=A and b!=B){
                dp[i+1][MP(a,b)]-=(dp[i-1][MP(a-1,b-1)]*(a-1)*(b-1));
            }
        }
        #endif
    }
    cout<<dp[(D+C)-(B+A)][MP(C,D)]<<endl; 
    #if 0
    REP(i,(D+C)-(B+A)+1){
        for(auto j=dp[i].begin();j!=dp[i].end();j++){
            ll a,b;a=j->F.F;b=j->F.S;
            cout << a << " " << b << " " << j->S << endl;
        }
    }
    #endif
}

Submission status: Runtime Error

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: Runtime Error

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: Runtime Error

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

j=0
for i in range(a,3003-a):
    dp[a+j][b+i+1]=((dp[a+j][b+i])*(a+1+j)%mod)
    for j in range(b,3003-b):
        dp[a+1+j][b+i]=((dp[a+j][b+i]*(b+i))%mod)
        #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: Runtime Error

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):
    dp[a+1+j][b+i+1]=((dp[a+1+j][b+i])*(a+1+j)%mod)
    for j in range(b,3003-b):
        dp[a+1+j][b+i]=((dp[a+j][b+i]*(b+i))%mod)
        #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: Runtime Error

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):
    dp[a+1+j][b+i+1]=((dp[a+1+j][b+i])*(a+1+j)%mod
    for j in range(b,3003-b):
        dp[a+1+j][b+i]=((dp[a+j][b+i]*(b+i))%mod
        #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: Runtime Error

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