题解"/>
Atcoder 2649 11 题解
题意简述
长度为n+1的序列a.其中[1…n]每个数都至少出现一次. (n<=1e5),对每个k从1到n+1,询问长度为k的不同的子序列有多少个?答案膜 1 0 9 + 7 10^9+7 109+7
(所以你要输出 n + 1 n+1 n+1行)
(又是蒯的)
思路框架
对于每个 k k k:显然有且仅有一个数字出现两次。找到这两个位置,设为 p 1 , p 2 p1,p2 p1,p2,然后答案就是 C n + 1 k − C n − p 2 + p 1 k − 1 C_{n+1}^{k}-C_{n-p2+p1}^{k-1} Cn+1k−Cn−p2+p1k−1
具体思路
首先,如果我们没有那个重复的式子,显然答案是 C n + 1 k C_{n+1}^k Cn+1
更多推荐
Atcoder 2649 11 题解
发布评论