过题数 |
排名 |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
4 |
635 |
√ |
B |
|
√ |
|
|
|
√ |
|
√ |
|
|
|
1 2 3 4 5 6
| |过题数|排名|A|B|C|D|E|F|G|H|I|J|K|L|M| |-----|----|-|-|-|-|-|-|-|-|-|-|-|-|-| | | | | | | | | | | | | | | | | √ 赛时过了 B 补题过了
|
B
有 2n 堆纸牌,每次抽到 i>n 就猜测下一张比这张小,否则下一张比这张大,询问在每种排列下一共能抽到多少张。第一张只用抓不用猜。
手推一下有个重要的性质,低于n只能猜大,大于只能猜小,因此我们一定可以分成很多个连续上升或者连续下降的序列。并且这些序列都是大于 n 或者小于等于 n 的。(不符合这个性质的一定在结尾或者开头,我们把它放在上一个序列依然是连续的。)
考虑 fi,j,0/1 表示抓了 i 张小于等于 n ,j 张大于 n 并且最后结尾是小于/大于的方案数。
然后统计对答案的贡献即可。
计算贡献的方式:已经放好了 i,j ,下一张对答案的贡献。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| #include<bits/stdc++.h> #define int long long
using namespace std;
const int maxn=660;
int f[maxn][maxn][2]; int T,c[maxn][maxn],modp,p[maxn]; int ans=0,n;
void init() { p[0]=1; for(int i=1;i<=n*2;i++) p[i]=i*p[i-1]%modp; c[0][0]=1; for(int i=1;i<=n*2;i++) for(int j=0;j<=i;j++) { if(j==0) c[i][j]=1; else c[i][j]=(c[i-1][j-1]+c[i-1][j])%modp; } for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) f[i][j][0]=f[i][j][1]=0; f[0][0][0]=f[0][0][1]=1; }
signed main() { cin>>T; while(T--) { cin>>n>>modp; init(); ans=0; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) { if(i==0&&j==0) continue; for(int k=1;k<=i;k++) f[i][j][0]=(f[i][j][0]+f[i-k][j][1]*c[n-i+k][k]%modp)%modp; for(int k=1;k<=j;k++) f[i][j][1]=(f[i][j][1]+f[i][j-k][0]*c[n-j+k][k]%modp)%modp; if(i==n&&j==n) continue; ans=(ans+p[n*2-i-j]*(f[i][j][0]+f[i][j][1]))%modp; } ans=(ans+p[n*2])%modp; cout<<ans<<'\n'; } }
|