阿里淘天集团笔试 0902 题解分享

#阿里#单选和多选还挺难的。。。
编程题不能在本地ide写差评
T1
给一个长度为N的数组，求a_i+a_j=a_k^a_l的四元对数(i<j<k<l)
那么枚举个a_j 从左往右，然后动态维护右边a_k^a_l=x的数量，由于a<=100,所以a_k^a_l<=128，只要开个128的数组维护
然后枚举ai+a_j，直接乘上右边的a_k^a_l=a_i+a_j的数量就行了，复杂度O（n^2）
T2
长度为n的数组, 1<=a_i<=m ,a_i%i==0 ,(a1+a2+..a_n ）%n==0 ，n,m<=1000，求方案数
直接dp[i][j]表示安排了前i位，然后(a1+a2+...a_i)%n==j的方案数，由于枚举a_i必须是i的倍数
那么复杂度就是调和级数O（nmlnm）
T3
字符串，有多少个子序列，首尾一样
对于一对相同的字母，假设他们坐标为i和j， 以他们为首尾的子序列共有2^(j-i-1)
所以只要把相同的字母的下标搞到一起来选，枚举左端点，同时维护所有右端点到当前左端点的2^(j-i-1)之和，
左端点向右移动，就减掉这一段，剩下的总和除以2^(j-1)，这里预处理一下幂次%mod和幂次的逆元%mod就行了
如果不会逆元不想搞除法，就让左端点从右往左移动，这样就先乘后加上一段新的，比较方便
复杂度O(n)
#阿里##阿里秋招##秋招##阿里笔试##阿里淘天##秋招笔试#