START200——Permutation Counting (Easy)

思路讲解

题意就是计数问题，求满足$\forall i\in[2,N],\ \ P_{i-1}+P_i\not\equiv0\pmod K$ 的排列有几个？

首先，看题面，我们发现 $∑_{i=1}^{T}N_i≤2e5$，因此最终算法是$O(n\log n)$ 或者 $O(n)$。

然后我们猛然发现，$K=3$，确实，我们觉得束手无策是对的，因为如果没有这个条件，是3000+的题目。

那么看着这个数据，我们容易想到dp，$dp[i]$ 表示$1\cdots i$ 这个排列有可能的总数量（状态定义与答案保持一致）。

但是我们发现这个转移还是比较难的，因为我们用插入一个数字的想法的话，不仅就是说这个原来的合法序列上能够插入，原来的非法序列上也能够插入，变为合法序列，这就导致dp数组存储的信息没有什么意义。

因此，我们还是回到组合数学上，可以令除以3之后余数为0，1，2的分别为$r_0,r_1,r_2$。

不难发现，$r_0$ 和 $r_0$ 不能放在一起，$r_1$ 和 $r_2$ 也不能放在一起。那么总体结构类似于 $r_1|r_0|r_2$ 或者 $r_2|r_0|r_1$ 。

不难发现，如果我们直接固定 $r_0$，接着去填充 $r_1$ 和 $r_2 $，这相当于解决：

有$r_0+1$个盒子，其中有$r_0-1$个必须装有球，且一个盒子装的球必须为同一种（一共只有两种），注意，可以理解为球带有编号，且放入盒子的顺序是重要的，盒子也是不同的。

这个问题是比较难解决的，不如我们先确定$r_1$和$r_2$，然后填充 $r_0$ 这样会简单很多。

// 我们按照交替进行分类，就是1-0-2-0-1是可以的，1-0-1-0-2，我们按照1-0-2处理。
// 为什么那？说多了都是泪，详细可以看下面的踩坑代码。
FOR(i,2,r0+1){
    if(i&1){
        for(int j=i/2;j<=i/2+1;++j){
            ll other=i-j;
            // stars and bars
            ll lans=CC(r1-1,j-1)*CC(r2-1,other-1)%mod;
            // 多余0的摆放
            // 一共有r1+r2+1个位置，有i-1个位置被用掉了，剩余r0-i+1个0
            lans*=CC(r1+r2+1-i+1,r0-i+1);lans%=mod;
            ans+=lans;
            ans%=mod;
        }
    }else{
        for(int j=i/2;j<=i/2;j++){
            ll other=i-j;
            // stars and bars
            ll lans=CC(r1-1,j-1)*CC(r2-1,other-1)%mod;
            if(j==i/2) lans*=2;
            lans*=CC(r1+r2+1-i+1,r0-i+1);lans%=mod;
            ans+=lans;
            ans%=mod;
        }
    }
}

将1-0-1-0-2和1-0-1-0-2视为相同（r1的位置可以重新排列，但这属于重复计数）的缺点。实际上，如果我们在最后乘以P(r1,r1)，我们就将r1的块视为相同。当然，r2也是相同的。

AC代码

源代码

心路历程（WA，TLE，MLE……）