\(T1\)题面，由于是正方形，我们不需要枚举左上和右下两个端点，只需枚举左上端点和正方形边长，而正方形边长如果用二分枚举，常数大，过不了。这里考虑矩形中一个技巧，即在矩形中充分利用已经求过的信息，故可以想到递推，设\(l[i][j]\)表示\((i,j)\)为左端点最大正方形长度，则\(l[i][j]\)最少为\(l[i-1][j]-1\)(即被包含），然后枚举\(l[i][j]\)，复杂度均摊不会炸。
\(T2\)题面，题面一眼换根\(dp\)，看到\(k\)次方可想二项式定理，慢慢推吧。换根\(dp\)讲解