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