签到签的飞快，然后慢慢滑出第一页……(ノへ￣、)
# 题面
> HDU 6880
点击展开/折叠 题面翻译
有一个 $1\sim n$ 的排列，已知该排列相邻两个元素的大小关系，求有多少种满足条件的排列。
# 解析
求排列的数量难点在于不便于统计哪些数已经出现过；注意到每个限制条件其实是相对独立的，用重编号法就可以解决这个问题。
可以倒过来理解，设 $f_{i,j}$ 表示 $1\sim i$ 的排列满足前 $i-1$ 个限制，且最后一个元素为 $j$ 的方案数。转移则考虑直接删掉最后一个元素，然后把剩下的 $i-1$ 个元素按照大小关系重新编号为 $1\sim i-1$。
- 若是 $a_{i-1}>a_i$，则转移则为 $f_{i-1,k}\to f_{i,j}$（$k< j$）；
- 若是 $a_{i-1}< a_i$，则转移则为 $f_{i-1,k}\to f_{i,j}$（$k\ge j$），重标号后大小为 $j$ 的原本是 $j+1$，其实比 $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
|
#include<bits/stdc++.h>
using namespace std;
#define cs const int &
const int N=5005,MOD=1e9+7;
inline int Add(cs a,cs b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(cs a,cs b){return a-b<0? a-b+MOD:a-b;};
inline int Mul(cs a,cs b){return 1ll*a*b%MOD;}
int cas,n;
int f[2][N];
inline int Read(){
register int r=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r;
}
int main(){
cas=Read();
while(cas--){
n=Read();
for(int i=1;i<=n;i++) f[1][i]=0;
f[1][1]=1;
for(int i=2;i<=n;i++){
int num=Read(),I=i&1,J=!I;
for(int j=1;j<=n;j++) f[I][j]=0;
int sum=0;
if(num==0)
for(int j=1;j<=i;j++){
sum=Add(sum,f[J][j]);
f[I][j+1]=sum;
}
else
for(int j=i-1;j>=1;j--){
sum=Add(sum,f[J][j]);
f[I][j]=sum;
}
}
int ans=0;
for(int i=1;i<=n;i++) ans=Add(ans,f[n&1][i]);
printf("%d\n",ans);
}
return 0;
}
|
THE END
Thanks for reading!
> Linked OI Diary-Madia Lemon-Bilibili