题目传送门
引
很有意思的计数题
解法
考虑经过操作后得到的排列的性质
性质1:
设
p
r
e
(
i
)
pre(i)
pre(i):前i个位置的最大值,则不会出现超过3个的连续位置的
p
r
e
pre
pre相同
必要性:
考虑反证,若有超过
3
3
3个的连续位置的
p
r
e
pre
pre相同,那么至少有连续有连续三次选择了比第一次选择要小的数,那么至少一个块的长度为
4
4
4,题目中规定块长为
3
3
3,因此不合法
充分性:
发现没有充分性,比如:
{
2
,
1
,
4
,
3
,
6
,
5
}
\{2,1,4,3,6,5\}
{2,1,4,3,6,5},手玩模拟一下就会发现有问题
性质2:
若排列总长为
3
N
3N
3N,
i
i
i个的连续位置的
p
r
e
pre
pre相同的个数为
c
n
t
i
cnt_i
cnti,那么
c
n
t
2
≤
N
−
c
n
t
3
cnt_2\le N-cnt_3
cnt2≤N−cnt3
必要性:
对于
c
n
t
2
cnt_2
cnt2与
c
n
t
3
cnt_3
cnt3来说,他们对应的块内的大小关系是一定的,所以可得
c
n
t
2
+
c
n
t
3
≤
N
cnt_2+cnt_3\le N
cnt2+cnt3≤N,移项就行了
我们可以化简:
c
n
t
2
≤
N
−
c
n
t
3
⇒
3
c
n
t
2
≤
3
N
−
3
c
n
t
3
⇒
3
c
n
t
2
≤
(
c
n
t
1
+
2
c
n
t
2
+
3
c
n
t
3
)
−
3
c
n
t
3
⇒
移项得
c
n
t
2
≤
c
n
t
1
\begin{aligned} &cnt_2\le N-cnt_3\\ \Rightarrow&3cnt_2\le 3N-3cnt_3\\ \Rightarrow&3cnt_2\le (cnt_1+2cnt_2+3cnt_3)-3cnt_3\\ \Rightarrow^{移项得}&cnt_2\le cnt_1 \end{aligned}
⇒⇒⇒移项得cnt2≤N−cnt33cnt2≤3N−3cnt33cnt2≤(cnt1+2cnt2+3cnt3)−3cnt3cnt2≤cnt1
最后我们发现性质1和性质2加起来就有了充分性
状态设计:
f
i
,
j
:
前
i
个数,
c
n
t
1
−
c
n
t
2
=
j
的方案数
f_{i,j}:前i个数,cnt_1-cnt_2=j的方案数
fi,j:前i个数,cnt1−cnt2=j的方案数
显然
a
n
s
=
∑
k
=
0
3
n
f
3
n
,
k
ans=\sum_{k=0}^{3n} f_{3n,k}
ans=∑k=03nf3n,k
状态转移:
考虑从小到大放数,对放
1
/
2
/
3
1/2/3
1/2/3个数分别考虑
f
i
,
j
→
f
i
+
1
,
j
+
1
f
i
,
j
→
f
i
+
2
,
j
−
1
∗
(
i
−
1
)
f
i
,
j
→
f
i
+
3
,
j
∗
(
i
−
1
)
∗
(
i
−
2
)
\begin{aligned} &f_{i,j}\to f_{i+1,j+1}\\ &f_{i,j}\to f_{i+2,j-1}*(i-1)\\ &f_{i,j}\to f_{i+3,j}*(i-1)*(i-2) \end{aligned}
fi,j→fi+1,j+1fi,j→fi+2,j−1∗(i−1)fi,j→fi+3,j∗(i−1)∗(i−2)
就好了
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);
}