AtCoder Beginner Contest 066（CD)

AtCoder Beginner Contest 066 （CD)

C - pushpush

思路：双端队列+指针指向即可。

D - 11

思路：组合数学。

考虑对于$k$用所有方案数$-$重复的方案数。

总方案数为：$C(n+1,k)$

假设重复的那个数为$x$，两个数的位置分别为：$p_1<p_2$

当且仅当所选择的$k$个数只包含一个$x$，且不含$(p_1,p_2)$之间的数则方案会重复。

所以重复的方案数等价为：从$n+1-(p_2-p_1+1)$个数中选择$k-1$个数 (因为$x$必须选)

即：$C(n-(p_2-p_1),k-1)$

所以对于$k$，答案为：$C(n+1,k)-C(n-(p_2-p_1),k-1)$

可用费马小定理或者阶乘逆元递推即可。

fac[0]=1; for(int i=1;i<=n+1;i++){ scanf("%d",&a[i]); if(vis[a[i]]) d=(i-vis[a[i]]); vis[a[i]]=i; fac[i]=fac[i-1]*i%mod; } for(int i=1;i<=n+1;i++){ printf("%lld\n",((C(n+1,i)-C(n-d,i-1))%mod+mod)%mod); }