Day1

第一题

水题

第二题

题意:一个n*m的字符矩阵从左上到右下,经过字符形成回文串的路径数。n≤500

回文串,考虑两段往中间DP。

f[k][x][y]表示走了k步,左上点横坐标为x,右下点横坐标为y的路径数。

两端2*2四种情况转移,k步这维滚动。

第三题

题意:区间加数,区间覆盖,询问区间x次幂和。n≤10^5。

主要难点在区间加数时维护x次幂和……实际上就是简单的二项式展开。

Σ(a+b)^n=Σ[ΣC(n,r)*a^(n-r)*b^r]=Σ[C(n,r)*Σa^(n-r)*b^r]  r=0~n

只要维护x次幂和就好了。

坑:枚举排列!!!

05-17 13:18