[agc019f]Yes or No

• 题目链接

  agc019f

• 题目大意

  有一长为 (N+M) 的 (01) 序列，其中恰有 (N) 个 (1) 和 (M) 个 (0)，顺序未知。

  进行 (N+M) 次操作，每次回答 (0) 或 (1)，会给出是否匹配。

  求在最优策略下，匹配个数的期望。答案对 (998244353) 取模。

  (N,Mle 5 imes 10^5)

  部分分：(N=Mspace andspace N,Mle 10^5)

• 题解

  首先题目可以转化为在一个 (N imes M) 的矩形上行走，对于一个点 ((i,j))，其权值为 (frac{max(i,j)}{i+j}) 。求的就是路径的期望权值，也就是所有路径的权值和。

  自然想到对 (i+j=k) 的统一算，但仍然不是很好算。

  我们考虑 (k o k+1) 的过程，发现只有经过 (y=x) 以下的水平线和其以上的竖直线才会令答案加一。那么我们对水平和竖直分开算。

  以水平线为例，若我们将水平线缩点，发现这是计数经过点 ((i,j)space (i+j=kspace andspace ige j)) 的路径。

  同样考虑 (k o k+1) 的过程，发现可以直接通过组合数加减得到。

  那么我们就可以 (O(1)) 统计出 (i+j=k) 的点 ((i,j)) 的权值和了。

  总复杂度 (O(N+M)) 。