[AGC043D] Merge Triplets

题目传送门

引

很有意思的计数题

解法

考虑经过操作后得到的排列的性质

---

性质1：
设$pre(i)$:前i个位置的最大值，则不会出现超过3个的连续位置的$pre$相同
必要性：
考虑反证，若有超过$3$个的连续位置的$pre$相同，那么至少有连续有连续三次选择了比第一次选择要小的数，那么至少一个块的长度为$4$,题目中规定块长为$3$，因此不合法
充分性：
发现没有充分性，比如： { 2 , 1 , 4 , 3 , 6 , 5 } \{2,1,4,3,6,5\} {2,1,4,3,6,5},手玩模拟一下就会发现有问题
性质2：
若排列总长为$3N$,$i$个的连续位置的$pre$相同的个数为$cn{t}_i$,那么$cn{t}_2\le N-cn{t}_3$
必要性：
对于$cn{t}_2$与$cn{t}_3$来说，他们对应的块内的大小关系是一定的，所以可得$cn{t}_2+cn{t}_3\le N$,移项就行了
我们可以化简：
$$\begin{array}{rl}& cn{t}_2\le N-cn{t}_3\\ \Rightarrow & 3cn{t}_2\le 3N-3cn{t}_3\\ \Rightarrow & 3cn{t}_2\le (cn{t}_1+2cn{t}_2+3cn{t}_3)-3cn{t}_3\\ {\Rightarrow }^{移项得}& cn{t}_2\le cn{t}_1\end{array}$$

最后我们发现性质1和性质2加起来就有了充分性

---

状态设计：

$f_{i,j}:前i个数，cn{t}_1-cn{t}_2=j的方案数$
显然$ans={\sum }_{k=0}^{3n}{f}_{3n,k}$

状态转移：

考虑从小到大放数，对放$1/2/3$个数分别考虑
$$\begin{array}{rl}& f_{i,j}\to f_{i+1，j+1}\\ & f_{i,j}\to f_{i+2,j-1}\ast (i-1)\\ & f_{i,j}\to f_{i+3，j}\ast (i-1)\ast (i-2)\end{array}$$
就好了

code:

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 7, M = N * 3;
typedef long long ll;
int n,mod,ans;
int f[M][M<<1];
int ad(int x,int y){ return (1ll*x+1ll*y)%mod; }
void work(int i,int j){f[i+1][j+1+M]=ad(f[i+1][j+1+M],f[i][j+M]);f[i+2][j-1+M]=ad(f[i+2][j-1+M],1ll*f[i][j+M]*(i+1)%mod);f[i+3][j+M]=ad(f[i+3][j+M],1ll*f[i][j+M]*(i+1)%mod*(i+2)%mod);
}
int main() {scanf("%d%d",&n,&mod); n=n*3;f[0][M]=1;for(int i=0;i<n;i++) for(int j=-i;j<=i;j++) work(i,j);for(int i=0;i<=n;i++) ans=ad(ans,f[n][i+M]);printf("%d\n",ans);
}

---

TXL