广东网站建设制作,广东省自然资源厅事务中心,分类id wordpress,完美动力培训机构传送门
前题提要:没得说,赛时根本没想到dp,赛后翻各大题解看了很久,终于懂了dp的做法,故准备写一篇题解.
首先,先定义一下我们的 d p dp dp方程,考虑将处于 [ 1 , n ] [1,n] [1,n]的数当做小数,将处于 [ n 1 , 2 ∗ n ] [n1,2*n] [n1,2∗n]的数当做大数.那么对于我们的摸牌结…传送门
前题提要:没得说,赛时根本没想到dp,赛后翻各大题解看了很久,终于懂了dp的做法,故准备写一篇题解.
首先,先定义一下我们的 d p dp dp方程,考虑将处于 [ 1 , n ] [1,n] [1,n]的数当做小数,将处于 [ n 1 , 2 ∗ n ] [n1,2*n] [n1,2∗n]的数当做大数.那么对于我们的摸牌结果来说,必然是小数的递增序列大数的下降序列相交换的形式(例如n5,[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_{k1}^{i}dp[i-k][j][1]*C[n-(i-k)][k] dp[i][j][0]k1∑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_{k1}^{j}dp[i][j-k][0]*C[n-(j-k)][k] d[i][j][1]k1∑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 ) (ij-k-ij) (ij−k−ij)产生的方案数.不妨假设我们摸的 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 ij ij 所以此时的方案数就是(状态是 [ 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-(ij)]*(ij) dp[i−k][j][1]∗c[n−(i−k)][k]∗(k−1)∗fac[2∗n−(ij)]∗(ij)类似的,假如最后的序列是大数,那么方案数就是(状态是 [ 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-(ij)]*(ij) dp[i][j−k][0]∗c[n−(j−k)][k]∗(k−1)∗fac[2∗n−(ij)]∗(ij)
因为模数不确定,也就是不一定是素数,可能没有逆元,所以需要预处理组合数
至此,本题结束 下面是具体的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
inline void print(__int128 x){if(x0) {putchar(-);x-x;}if(x9) print(x/10);putchar(x%100);
}
#define maxn 1000000
#define int long long
const double eps1e-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个大数,k0代表末尾小,1代表末尾大
void init() {for(int i0;i2*n;i) {for(int j0;j2*n;j) {dp[i][j][0]dp[i][j][1]0;}}c[0][0]1;for(int i1;i2*n;i) {c[i][0]1;for(int 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) fac[i]fac[i-1]*i%mod;
}
signed main() {int Tread();while(T--) {nread();modread();init();int ans0;dp[0][0][0]dp[0][0][1]1;for(int i0;in;i) {for(int j0;jn;j) {for(int k1;ki;k) {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 0;
}
