아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

독한 댓글

시간 제한1초메모리 제한1024 MB

요약
댓글을 다운보트에 비례하는 확률로 하나씩 삭제할 때, 내가 쓴 N개의 댓글이 모두 지워질 때까지의 삭제 횟수 기댓값을 구한다.
난이도

보통10점 중 7점

유형
확률, 조합론, 수학, 동적 계획법
정답자
아직 제출이 없습니다

문제

블로그에 N+MN+M개의 독한 댓글이 달려 있다. 그중 NN개는 당신이 쓴 댓글이고, ii번째 댓글은 비추천 AiA_i개를 받았다. 나머지 MM개 중 ii번째 댓글은 비추천 BiB_i개를 받았다.

Mike는 다음 연산을 반복해서 댓글을 하나씩 지운다.

  • 남아 있는 댓글 중 하나를 무작위로 골라 지운다. 정확히는 남아 있는 댓글이 받은 비추천 수를 x1,x2,…,xkx_1,x_2,\ldots,x_k라 하면, ii번째 댓글을 xi/(∑1≤j≤kxj)x_i/\left(\sum_{1\leq j \leq k}x_j \right)의 확률로 고르고 지운다.

각 연산에서의 선택은 서로 독립이다.

Mike가 당신의 댓글을 모두 지울 때까지 수행할 연산 횟수의 기댓값을 구하시오. 답은 유리수이고, 평소처럼 998244353998244353으로 나눈 나머지를 출력하면 된다. 이 문제의 제약에서 그런 표현이 항상 가능함을 증명할 수 있다.

입력

첫째 줄에 정수 NN과 MM이 주어진다. (1≤N,M≤1001 \leq N,M \leq 100)

둘째 줄에 정수 A1,A2,…,ANA_1,A_2,\ldots,A_N이 주어진다. (1≤Ai≤1001 \leq A_i \leq 100)

셋째 줄에 정수 B1,B2,…,BMB_1,B_2,\ldots,B_M이 주어진다. (1≤Bi1 \leq B_i, ∑1≤i≤NAi+∑1≤i≤MBi<998244353\sum_{1 \leq i \leq N} A_i + \sum_{1 \leq i \leq M} B_i < 998244353)

출력

답을 출력한다.

예제3

  1. 예제 1

    입력
    1 2
    1
    1 1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    1 1
    2
    1
    
    예상 출력
    332748119
    
  3. 예제 3

    입력
    3 3
    2 3 5
    7 11 900000000
    
    예상 출력
    636512475