没保存代码，口胡一下第一题是A_n = 1 + (n + 1) * A_{n - 1}，递推即可。复杂度O(n)第二题是dfs找连通块，遍历到的红色点全部涂回白色，每一次找红色的点进行dfs，并统计一下连通块中点的数量，然后排序输出第k大即可。复杂度O(n)  （如果排序的话要加 m logm（m为连通块数），不过本来求第k大也有O(m)的解法，就是这里没必要用）第三题首先找长度为n的所有字串的美丽度之和。使用r[n], re[n], red[n]代表长度为n的所有子串出现'r', 're', 'red'的次数。分成前n-1位和最后一位去看。r的话，最后一位有三种选择，所以前n-1位r的总数量要乘3，然后再加上最后一位是r，前n-1位有3^(n-1)种选择。re的话，最后一位有三种选择，所以前n-1位re的总数量要乘3，然后再加上最后一位是e时，前n-1位中r的数量。red的话，最后一位有三种选择，所以前n-1位red的总数量要乘3，然后再加上最后一位是d时，前n-1位中re的数量。r[n] = r[n - 1] * 3 + 3^(n - 1)re[n] = re[n - 1] * 3 + r[n - 1]red[n] = red[n - 1] * 3 + re[n - 1]r[0] = re[0] = red[0] = 0从1开始递推。red[n]即长度为n所有字串的美丽度之和。然后开始找长度为n所有字串的权值之和。一共有3^n个串，其中含有的长度为k的子串有(n - k + 1)个，因此长度为n的字符串中，含有的长度为k的子串的个数一共是3^n * (n - k + 1)。又因为所有长度为k的子串出现的次数相等，因此每个长度为k的子串出现了3^(n - k) * (n - k + 1)次。所以直接计算sum{ red[k] * 3^(n - k) * (n - k + 1) }(3 <= k <= n)即可。注意一下取模时机，三个数相乘容易爆long long，每两个数相乘就取一下模。复杂度O(n)

开始找的太晚了，今天做百度笔试本来感觉做的还不错，做完在牛客网上搜一下才发现全是原题，都是kpi笔试感觉好像好多大厂都招满了？还有什么大中厂的暑期实习能投一下嘛