START200——Permutation Counting (Easy) · znzryb
## 思路讲解
题意就是计数问题，求满足$\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$ 这样会简单很多。
```cpp
// 我们按照交替进行分类，就是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代码
::: 源代码
```cpp
```
:::
## 心路历程（WA，TLE，MLE……）