think-cell Round 1 E. 2..3...4.... Wonderful! Wonderful!

· · 题解

枚举 k 和删除次数 i，一共 O(N\ln N)，每次 O(1) 计算方案。

答案不太好直接算合法方案数，正楠则反，考虑容斥，用总方案数 \binom{n}{2\times i\times k}，减去不合法的方案数。

不合法的序列满足所有保留的数要么在第 k 个删除的数的左边要么在第 2\times i\times k-k+1 个数的右边，注意到第 k 个到第 2\times i\times k-k+1 个删除的数是连续的一段，枚举这一段左端点 p，不合法的方案数为：

\sum\limits_{p=k}^{n-2\times i\times k+2\times k-1} \binom{p-1}{k-1}\binom{n-2\times i\times k+2\times k-1-p}{k-1}

注意到 p\in [1,k-1] 时，\binom{p-1}{k-1}=0，所以下界可以直接变成 1，所以不合法方案数为：

\sum\limits_{p=1}^{n-2\times i\times k+2\times k-1} \binom{p-1}{k-1}\binom{n-2\times i\times k+2\times k-1-p}{k-1}

稍微改写了一下：

\sum\limits_{p=1}^{n-2\times i\times k+2\times k-1} \binom{(-1)+p}{k-1}\binom{(n-2\times i\times k+2\times k-1)-p}{k-1}

注意到 -(-1)=1，所以原式满足上指标卷积的形式，所以：

\sum\limits_{p=1}^{n-2\times i\times j+2\times k-1} \binom{(-1)+p}{k-1}\binom{(n-2\times i\times k+2\times k-1)-p}{k-1}=\binom{n-2\times i\times k+2\times k-1}{2\times k-1}

这样就能简单计算了。

code：

for(int k=1;k*2<n;++k){
    LL ans=1;
    for(int i=1;2*k*i<=n;++i){
        ans=(ans+C(n,2*i*k)-C(n-2*i*k+2*k-1,2*k-1)+mod)%mod;
    }
    write(ans,' ');
    } 
}