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次幂和就好了。
坑:枚举排列!!!