传送门
前题提要:没得说,赛时根本没想到dp,赛后翻各大题解看了很久,终于懂了dp的做法,故准备写一篇题解.
首先,先定义一下我们的
d
p
dp
dp方程,考虑将处于
[
1
,
n
]
[1,n]
[1,n]的数当做小数,将处于
[
n
+
1
,
2
∗
n
]
[n+1,2*n]
[n+1,2∗n]的数当做大数.那么对于我们的摸牌结果来说,必然是小数的递增序列+大数的下降序列相交换的形式(例如n=5,[1,2,3,7,6])
那么我们可以得出一个
d
p
dp
dp方程,我们设
d
p
[
i
]
[
j
]
[
0
/
1
]
dp[i][j][0/1]
dp[i][j][0/1]当前摸到的牌中有
i
i
i段是小数序列,有
j
j
j段是大数序列,并且最后一段是大数/小数序列(0代表小数,1代表大数)的方案数.
此时考虑递推,对于每一个
[
i
,
j
]
[i,j]
[i,j]的状态,都可以通过上一次摸牌转移过来:
d
p
[
i
]
[
j
]
[
0
]
=
∑
k
=
1
i
d
p
[
i
−
k
]
[
j
]
[
1
]
∗
C
[
n
−
(
i
−
k
)
]
[
k
]
dp[i][j][0]=\sum_{k=1}^{i}dp[i-k][j][1]*C[n-(i-k)][k]
dp[i][j][0]=k=1∑idp[i−k][j][1]∗C[n−(i−k)][k]简单解释一下上述的递推式的意义.对于当前的状态,如果最后是小数序列,那么因为整个是大数与小数相交换的,所以上一次的状态必然是大数状态,并且此时我们从小数的堆中挑了
k
k
k个数加入到我们的手牌中,因为上一次状态小数的总个数是
n
−
(
i
−
k
)
n-(i-k)
n−(i−k),所以不难使用组合数得出上式.
类似的我们有:
d
[
i
]
[
j
]
[
1
]
=
∑
k
=
1
j
d
p
[
i
]
[
j
−
k
]
[
0
]
∗
C
[
n
−
(
j
−
k
)
]
[
k
]
d[i][j][1]=\sum_{k=1}^{j}dp[i][j-k][0]*C[n-(j-k)][k]
d[i][j][1]=k=1∑jdp[i][j−k][0]∗C[n−(j−k)][k]显然的,上面的递推式并没有完全解决我们的问题.因为我们的问题是总的摸牌数.上面求出的单单只是当前摸到某个状态的牌的方案数.那么对于每一次摸牌的结果,也就是每一个
d
p
[
i
]
[
j
]
[
0
/
1
]
dp[i][j][0/1]
dp[i][j][0/1]的状态,其实都是我们的答案.想象一下每一次状态其实我们都可以是一次技能的结束,也就是每一次状态我们都可能都止步于此.那么此时我们需要考虑的就是对于每一个状态我们停止的方案数.因为显然的,每一个状态我们有可能停止也有可能继续
考虑如上图的状态(分成三段),也就是
(
i
+
j
−
k
−
>
i
+
j
)
(i+j-k->i+j)
(i+j−k−>i+j)产生的方案数.不妨假设我们摸的
k
k
k是小数序列(大数与之类似)
因为我们需要恰好在摸完
k
k
k之后停止,那么说明我们的
k
k
k并不是一个完全递增序列,也就是最后一张牌比前面那张小.那么此时我们只有
k
−
1
k-1
k−1中方案.就比如摸到了
1
,
2
,
3
,
4
1,2,3,4
1,2,3,4,那么此时会停止的状态只有
1
,
2
,
4
,
3
∣
1
,
3
,
4
,
2
∣
2
,
3
,
4
,
1
1,2,4,3\;|\;1,3,4,2\;|\;2,3,4,1
1,2,4,3∣1,3,4,2∣2,3,4,1(注意我们除了最后一位需要保证递增,因为需要保证摸完k张牌).并且此时对于后面的所有剩下来的
2
n
−
i
−
j
2n-i-j
2n−i−j张没摸的牌来说,此时是可以随意摆放的(注意,我们是最终是所有的可能性的总和,所以即使牌没摸,但是不同摆放依旧算一种).所以此时的方案数乘上
(
2
n
−
i
−
j
)
!
(2n-i-j)!
(2n−i−j)!.然后我们需要的是总的摸牌数,那么对于每一个状态,我们都乘上该状态摸到的牌数,也就是
i
+
j
i+j
i+j
所以此时的方案数就是(状态是
[
i
,
j
,
0
]
[i,j,0]
[i,j,0]):
d
p
[
i
−
k
]
[
j
]
[
1
]
∗
c
[
n
−
(
i
−
k
)
]
[
k
]
∗
(
k
−
1
)
∗
f
a
c
[
2
∗
n
−
(
i
+
j
)
]
∗
(
i
+
j
)
dp[i-k][j][1]*c[n-(i-k)][k]*(k-1)*fac[2*n-(i+j)]*(i+j)
dp[i−k][j][1]∗c[n−(i−k)][k]∗(k−1)∗fac[2∗n−(i+j)]∗(i+j)类似的,假如最后的序列是大数,那么方案数就是(状态是
[
i
,
j
,
1
]
[i,j,1]
[i,j,1]):
d
p
[
i
]
[
j
−
k
]
[
0
]
∗
c
[
n
−
(
j
−
k
)
]
[
k
]
∗
(
k
−
1
)
∗
f
a
c
[
2
∗
n
−
(
i
+
j
)
]
∗
(
i
+
j
)
dp[i][j-k][0]*c[n-(j-k)][k]*(k-1)*fac[2*n-(i+j)]*(i+j)
dp[i][j−k][0]∗c[n−(j−k)][k]∗(k−1)∗fac[2∗n−(i+j)]∗(i+j)
因为模数不确定,也就是不一定是素数,可能没有逆元,所以需要预处理组合数
至此,本题结束
下面是具体的代码部分:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
inline void print(__int128 x){
if(x<0) {putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int c[610][610];int n,mod;int fac[maxn];
int dp[610][610][2];//i个小数,j个大数,k=0代表末尾小,1代表末尾大
void init() {
for(int i=0;i<=2*n;i++) {
for(int j=0;j<=2*n;j++) {
dp[i][j][0]=dp[i][j][1]=0;
}
}
c[0][0]=1;
for(int i=1;i<=2*n;i++) {
c[i][0]=1;
for(int j=1;j<=i;j++){
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
}
fac[0]=1;
for(int i=1;i<=2*n;i++) fac[i]=fac[i-1]*i%mod;
}
signed main() {
int T=read();
while(T--) {
n=read();mod=read();
init();
int ans=0;
dp[0][0][0]=dp[0][0][1]=1;
for(int i=0;i<=n;i++) {
for(int j=0;j<=n;j++) {
for(int k=1;k<=i;k++) {
dp[i][j][0]+=dp[i-k][j][1]*c[n-(i-k)][k]%mod;
dp[i][j][0]%=mod;
ans+=dp[i-k][j][1]*c[n-(i-k)][k]%mod*(k-1)%mod*fac[2*n-(i+j)]%mod*(i+j)%mod;
ans%=mod;
}
for(int k=1;k<=j;k++) {
dp[i][j][1]+=dp[i][j-k][0]*c[n-(j-k)][k]%mod;
dp[i][j][1]%=mod;
ans+=dp[i][j-k][0]*c[n-(j-k)][k]%mod*(k-1)%mod*fac[2*n-(i+j)]%mod*(i+j)%mod;
ans%=mod;
}
}
}
ans+=(dp[n][n][0]+dp[n][n][1])%mod*2*n%mod;ans%=mod;
cout<<ans<<endl;
}
return 0;
}
