2023牛客多校第三场 B.Auspiciousness

传送门

前题提要:没得说,赛时根本没想到dp,赛后翻各大题解看了很久,终于懂了dp的做法,故准备写一篇题解.

首先,先定义一下我们的$dp$方程,考虑将处于$[1,n]$的数当做小数,将处于$[n+1,2\ast n]$的数当做大数.那么对于我们的摸牌结果来说,必然是小数的递增序列+大数的下降序列相交换的形式(例如n=5,[1,2,3,7,6])
那么我们可以得出一个$dp$方程,我们设$dp[i][j][0/1]$当前摸到的牌中有$i$段是小数序列,有$j$段是大数序列,并且最后一段是大数/小数序列(0代表小数,1代表大数)的方案数.

此时考虑递推,对于每一个$[i,j]$的状态,都可以通过上一次摸牌转移过来:
$$dp[i][j][0]=\sum _{k=1}^{i}dp[i-k][j][1]\ast C[n-(i-k)][k]$$简单解释一下上述的递推式的意义.对于当前的状态,如果最后是小数序列,那么因为整个是大数与小数相交换的,所以上一次的状态必然是大数状态,并且此时我们从小数的堆中挑了$k$个数加入到我们的手牌中,因为上一次状态小数的总个数是$n-(i-k)$,所以不难使用组合数得出上式.
类似的我们有:
$$d[i][j][1]=\sum _{k=1}^{j}dp[i][j-k][0]\ast C[n-(j-k)][k]$$显然的,上面的递推式并没有完全解决我们的问题.因为我们的问题是总的摸牌数.上面求出的单单只是当前摸到某个状态的牌的方案数.那么对于每一次摸牌的结果,也就是每一个$dp[i][j][0/1]$的状态,其实都是我们的答案.想象一下每一次状态其实我们都可以是一次技能的结束,也就是每一次状态我们都可能都止步于此.那么此时我们需要考虑的就是对于每一个状态我们停止的方案数.因为显然的,每一个状态我们有可能停止也有可能继续

考虑如上图的状态(分成三段),也就是$(i+j-k->i+j)$产生的方案数.不妨假设我们摸的$k$是小数序列(大数与之类似)
因为我们需要恰好在摸完$k$之后停止,那么说明我们的$k$并不是一个完全递增序列,也就是最后一张牌比前面那张小.那么此时我们只有$k-1$中方案.就比如摸到了$1,2,3,4$,那么此时会停止的状态只有$1,2,4,3|1,3,4,2|2,3,4,1$(注意我们除了最后一位需要保证递增,因为需要保证摸完k张牌).并且此时对于后面的所有剩下来的$2n-i-j$张没摸的牌来说,此时是可以随意摆放的(注意,我们是最终是所有的可能性的总和,所以即使牌没摸,但是不同摆放依旧算一种).所以此时的方案数乘上$(2n-i-j)!$.然后我们需要的是总的摸牌数,那么对于每一个状态,我们都乘上该状态摸到的牌数,也就是$i+j$
所以此时的方案数就是(状态是$[i,j,0]$):$$dp[i-k][j][1]\ast c[n-(i-k)][k]\ast (k-1)\ast fac[2\ast n-(i+j)]\ast (i+j)$$类似的,假如最后的序列是大数,那么方案数就是(状态是$[i,j,1]$):$$dp[i][j-k][0]\ast c[n-(j-k)][k]\ast (k-1)\ast fac[2\ast n-(i+j)]\ast (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;
}