考试过程
看完题目感觉可做，心态没什么问题，T1正常思考，想到了一个伪的复杂度，以为只能过200的
但是造了组4000的发现超级快，然后就以为没有问题，就没有再看，现在想想真天真啊
T2感觉很可做显然是要分解质因数或者线筛什么的，但是1e9怎么分？
就先开了个桶，骗了20分，感觉贡献算少了，幸亏写了个对拍，
然后觉得不能一看T3就弃掉，仔细一看发现暴力dp好多分，又一看发现能有60分十分开心，又写了个对拍
幸亏最后看了眼T3，以后千万不能再凭经验做题了！
对于所有题目不要在深入思考前就妄下定论
lemon评测T3挂了！T3没有算空间啊啊啊！
第一次被卡了空间！！以后每一道题目都要去算空间复杂度！！！
题解
T1「贪心」「二分答案」
考场上觉得$k$次交换比较困难，于是就想到了要二分答案去验证是否小于等于k次
验证：枚举哪种字母，然后去看这种字母拼成$mid$长度的最小代价，从前往后去枚举每一段
现在的复杂度已经是$O(Nlog{N})$了
在去找最小次数的时候，由于没想着打正解，所以我考场上的做法是$O(N^2)$的，
首先有个贪心很常见的那种，中间点最优，那么是距离的中间点，还是字母的中间点呢？
题解的贪心：最终的形态中，必定有一段字母是不动的，所以字母的中间点不动一定不会更劣
然后$skyh$巨佬写了个前缀和就成$O(1)$ 的了。所以正解的O(N^2)的变成了$O(Nlog{N})$
T2「试除法」
反正是根号分解的思想，所以就暂且叫做试除法吧
70opts做法是，先用线筛筛出来根号内的所有质数，
对于每个a_i我们把它里面的所有平方因子给除去
最后省下的那些只有相等的才能做贡献
优化成100opts：
我们想少筛一点会发生什么，也就是只筛到$sqrt[3]{m}$
考虑最后剩下的数是x=p^2*k, $p > sqrt[3]{m}$
那么 $k > sqrt[3]{m}$也就是说k会在之前枚举到，那么我删去之后最后只会剩p^2了
具体实现：初始tmp=a_i，质因数我们只枚举到$sqrt[3]{m}$，
tmp和原数的平方因子干掉，剩下的单个因子，我们让x除去，
最后剩的x只会是p^2,然后删去就好了
T3「DP」「容斥」「组合数学」
n==0的情况显然是个组合数学，
d==2 $C(a1+a2,a1)$
d==3 $C(a1+a2+a3,a1) imes C(a2+a3,a2)$化简之后$(a1+a2+a3)!/(a1!*a2!*a3!)$
依次类推$sum {a_i}/ prod{a_i}$
n!=0的情况怎么办？我们考虑用合法的情况减去不合法的
f[i]表示考虑到第i个点的方案数，其中点0是A起点，n+1是B终点
$f[i]=cal(0,i)-sum{f[j]*cal(j,i)}$
$cal(j,i)$表示从j到i的方案数,j必须满足所有的d维都不大于i