题解"/>
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 题解
发布评论