ARC068D Solitaire

feecle6418 · 2022-03-11 14:53:05 · 题解

经过观察发现，设 f(n,k) 为答案，有

f(n,1)=2^{n-2}

f(n,n)=f(n,n-1)

f(n,k)=f(n,k-1)\times \dfrac{(n+k-2)(n-k+1)}{2(k-1)(n-k+2)}\ (1<k<n)

直接计算即可，复杂度线性。套用快速阶乘算法可以做到 O(\sqrt n\log n)。