月度归档:2018年06月

2018 ACM-ICPC China Jiangsu Provincial Programming Contest

A. 签到题

B. 滚动数组DP

C. ???

D. \( \frac{(\sum_{i=1}^n U[i])!}{\prod_{i=1}^n U[i]!} \)

E. Catalan数?

F. 预处理dfs序,按照F的值的顺序更新树状数组求方案数

G. 每M个数分为一组,组内求出所有前缀积和后缀积。每个window就可以拆成一个前缀积和一个后缀积的乘积。

H. Berlekamp-Massey模板题

I. 将矩阵乘法的定义中,乘法改为加法,加法改为max,然后求个矩乘快速幂

J. 高精度

K. 求出最短路图中除起点外所有点的入度之积