小红书4.23笔试 3/3 口胡题解

没保存代码，口胡一下 #小红书# #笔试#

第一题是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)