解释一下上述的递推式的意义.对于当前的状态,如果最后是小数序列,那么因为整个是大数与小数相交换的,所以上一次的状态必然是大数状态,并且此时我们从小数的堆中挑了

n-(i-k)

d[i][j][1]\sum_{k1}^{j}dp[i][j-k][0]*C[n-(j-k)][k]

d[i][j][1]k1∑j​dp[i][j−k][0]∗C[n−(j−k)][k]显然的,上面的递推式并没有完全解决我们的问题.因为我们的问题是总的摸牌数.上面求出的单单只是当前摸到某个状态的牌的方案数.那么对于每一次摸牌的结果,也就是每一个

dp[i][j][0/1]

dp[i][j][0/1]的状态,其实都是我们的答案.想象一下每一次状态其实我们都可以是一次技能的结束,也就是每一次状态我们都可能都止步于此.那么此时我们需要考虑的就是对于每一个状态我们停止的方案数.因为显然的,每一个状态我们有可能停止也有可能继续

(ij-k-ij)

k并不是一个完全递增序列,也就是最后一张牌比前面那张小.那么此时我们只有

k-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张牌).并且此时对于后面的所有剩下来的

2n-i-j

2n−i−j张没摸的牌来说,此时是可以随意摆放的(注意,我们是最终是所有的可能性的总和,所以即使牌没摸,但是不同摆放依旧算一种).所以此时的方案数乘上

(2n-i-j)!

(2n−i−j)!.然后我们需要的是总的摸牌数,那么对于每一个状态,我们都乘上该状态摸到的牌数,也就是

[i,j,0]

dp[i-k][j][1]*c[n-(i-k)][k]*(k-1)*fac[2*n-(ij)]*(ij)

dp[i−k][j][1]∗c[n−(i−k)][k]∗(k−1)∗fac[2∗n−(ij)]∗(ij)类似的,假如最后的序列是大数,那么方案数就是(状态是

[i,j,1]

dp[i][j-k][0]*c[n-(j-k)][k]*(k-1)*fac[2*n-(ij)]*(ij)

dp[i][j−k][0]∗c[n−(j−k)][k]∗(k−1)∗fac[2∗n−(ij)]∗(ij)

因为模数不确定,也就是不一定是素数,可能没有逆元,所以需要预处理组合数

至此,本题结束

chgetchar();for(;ch9||ch0;chgetchar())

if(ch-)

dp[610][610][2];//i个小数,j个大数,k0代表末尾小,1代表末尾大

void

{dp[i][j][0]dp[i][j][1]0;}}c[0][0]1;for(int

i1;i2*n;i)

j1;ji;j){c[i][j](c[i-1][j-1]c[i-1][j])%mod;}}fac[0]1;for(int

i1;i2*n;i)

ans0;dp[0][0][0]dp[0][0][1]1;for(int

i0;in;i)

{dp[i][j][0]dp[i-k][j][1]*c[n-(i-k)][k]%mod;dp[i][j][0]%mod;ansdp[i-k][j][1]*c[n-(i-k)][k]%mod*(k-1)%mod*fac[2*n-(ij)]%mod*(ij)%mod;ans%mod;}for(int

k1;kj;k)

{dp[i][j][1]dp[i][j-k][0]*c[n-(j-k)][k]%mod;dp[i][j][1]%mod;ansdp[i][j-k][0]*c[n-(j-k)][k]%mod*(k-1)%mod*fac[2*n-(ij)]%mod*(ij)%mod;ans%mod;}}}ans(dp[n][n][0]dp[n][n][1])%mod*2*n%mod;ans%mod;coutansendl;}return