T1：
枚举中心所在位置，每次贪心找到左右最近的一个相同字符移动。
可以用单调指针扫。
时间复杂度$O(n^2)$。
T2：
两个数的乘积为平方数，那么这两个数各自去掉平方因子后相等。
去掉平方因子后可以用map统计答案。
对于普通的$O(sqrt{p})$试除法，复杂度不允许，就算将所有的质数筛出后枚举质数也会超时。
筛出质数是肯定要的，考虑优化试除。
我们只关心平方因子，所以可以用$O(p^{frac{1}{3}})$的试除。
先用小于$p^{frac{1}{3}}$的质数筛一遍，那么剩下的数不会含有小于$p^{frac{1}{3}}$的质因子。
然后就只有两种情况，即一个大质数和一个质数的平方。
开根再乘判一下就行。
时间复杂度$O(np^{frac{1}{3}})$。
T3：
d维空间中两点之间的路径数：
设两个点每一维的坐标差为$a_i$，则$ans=frac{(sum limits_{i=1}^d a_i)!}{prod limits_{i=1}^d a_i!}$。
设$dp[i]$表示由起点到$i$的方案数，$S$为能到达$i$的点集。
$dp[1]=-1$
$dp[i]=-sum limits_{j in S}dp[j]*calc(j,i)$
其实就是容斥。
时间复杂度$O(n^2d)$。