题解 BZOJ 1931 [Shoi2007]Permutation 有序的计数

题目

第一问很简单。。
来看第二问求排名。
我们可以用数位dp的思想:计算固定前面一些位,后面可以随意填的数量。
假设已经固定了前i位,数组$use[x]$表示x是否被使用过。
设tot为满足$use[x]==0且x>i$ $ x$的数量。
那么最多可以有tot个位置能够产生有序数,
于是当前就应该有$C[tot][K]*F[n-i-1-K][tot-K]$个数字。

$F[i][j]$表示长度为i个数字,其中j个在1-i之间,全错位排列的数量。

$F[i][j]$数组类似错位排序的递推。

$F[i][0]=i!$
$ F[i][j]=F[i-1][j-1]*(i-j)+F[i-1][j-2]*(j-1) $

具体就是把新添加的位置填哪些数分开讨论下。
(然后加个高精度特技就能A了。

code:

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
struct N{
int a[205];
friend N operator + (const N&a,const N&b){
N c;
for(int i=0;i<=204;i++) c.a[i]=a.a[i]+b.a[i];
for(int i=0;i<204;i++) c.a[i+1]+=c.a[i]/10,c.a[i]%=10;
return c;
}
friend N operator * (const N&a,int x){
N c;
for(int i=0;i<=204;i++) c.a[i]=a.a[i]*x;
for(int i=0;i<204;i++) c.a[i+1]+=c.a[i]/10,c.a[i]%=10;
return c;
}
friend N operator * (const N&a,const N&b){
N c;
memset(c.a,0,sizeof c.a);
for(int i=0;i<=100;i++){
for(int j=0;j<=100;j++){
c.a[i+j]+=a.a[i]*b.a[j];
}
}
return c;
}
}d[65],c[65][65],F[65][65],f[65],ans;
int n;
int a[200];
bool use[200];
int p;
int main(){
d[0].a[0]=1;d[1].a[0]=0;d[2].a[0]=1;
for(int i=3;i<=64;i++) d[i]=(d[i-1]+d[i-2])*(i-1);
f[0].a[0]=1;
for(int i=1;i<=64;i++) f[i]=f[i-1]*i;
for(int i=0;i<=64;i++){
c[i][0].a[0]=1;
for(int j=1;j<=i;j++){
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
}
for(int i=0;i<=64;i++) F[i][0]=f[i];
for(int i=1;i<=64;i++){
for(int j=1;j<=i;j++){
F[i][j]=F[i-1][j-1]*(i-j)+F[i-1][j-2]*(j-1);
}
}
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]),p+=(a[i]==i);
printf("%d ",p);
int K=p;
for(int i=0;i<n;i++){
for(int j=0;j<a[i];j++){
if(use[j]) continue;
if(j==i) K--;
if(K<0){
K++;
continue;
}
use[j]=1;

int tot=0;
for(int k=i+1;k<n;k++){
if(!use[k]) tot++;
}
if(tot>=K){
ans=ans+c[tot][K]*F[n-i-1-K][tot-K];
}
use[j]=0;
if(j==i) K++;
}
if(a[i]==i) K--;
use[a[i]]=1;
}
int top=201;
while(top>1&&ans.a[top-1]==0) top--;
while(top>0) printf("%d",ans.a[--top]);
puts("");
return 0;
}

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框