非常神奇的连续段 dp！
题目链接。
题意
给定 和长度为 的序列 。
对于两个长为 的排列 ，我们设 。
称 是好的当且仅当对于每一个
的位置，在矩阵 中不存在一个 的正方形，覆盖了
这个位置，且这个正方形是一个单位矩阵或单位矩阵的镜像。
对好的 方案数计数。
。
题解
设排列 满足 ，那么 。
所以 是好的，当且仅当
中 这个数字所在的连续段长度不超过 。
那么我们只需要计算出合法的
数量，再乘上 ，就是答案了。
考虑连续段
dp，我们每一次按照从小到大的顺序，往序列中加入一个递增或递减的连续段。
考虑设加入之前，一共形成了
条链，那么有这么几种方案：
- 新加入的连续段单独成一条链；
- 新加入的连续段和之前的某一条链首尾相接；
- 新加入的连续段，两边各和之前的某一条链首位相接。
当将新加入的段和别的链拼起来时，需要满足这条链的这一段不能和新加入的连续段组成更大的连续段。
那么直接
表示加完前 个数字，当前有
条链，最新一个连续段完全没有影响／在边上／是一个单点且独立成段的方案数。
这样的话，直接枚举上一个连续段大小，做法就是 的了。
还可以注意到，对于一个固定的
来说，合法的
是一个后缀，所以直接前缀和优化转移即可。
时间复杂度 。
代码
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
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mod=998244353;
const int inv2=(mod+1)/2;
ll dp[5005][5005][3];
ll fp[2][5005][3];
int a[5005];
int n;
inline void Add(ll &a,ll b)
{
a+=b;
if(a>=mod) a-=mod;
}
int main()
{
n=read()+1;
for(int i=2;i<=n;i++) a[i]=read();
int now=0,lst=1;
dp[1][0][0]=1,fp[now][0][0]=1;
for(int r=2;r<=n;r++)
{
swap(now,lst);
memset(fp[now],0,sizeof(fp[now]));
for(int p=0;p<r;p++) for(int z=0;z<3;z++)
{
if(p) Add(fp[now][p-1][0],fp[lst][p][z]*(p-1)*(p-z)%mod);
Add(fp[now][p][1],fp[lst][p][z]*(2*p-z)%mod);
Add(fp[now][p+1][2],fp[lst][p][z]);
}
int w=0x3f3f3f3f,mi=0x3f3f3f3f;
for(int l=r;l;l--)
{
mi=min(mi,a[l]);
if(mi>=r-l+1) w=l;
}
for(int p=0;p<r;p++) for(int z=0;z<3;z++)
{
if(p) Add(fp[now][p-1][0],(dp[r-2][p][z]-dp[w-2][p][z]+mod)*(p-1)*(2*p-z)%mod);
Add(fp[now][p][1],(dp[r-2][p][z]-dp[w-2][p][z]+mod)*(2*p-z)%mod);
Add(fp[now][p][0],(dp[r-2][p][z]-dp[w-2][p][z]+mod)*2*p%mod);
Add(fp[now][p+1][1],(dp[r-2][p][z]-dp[w-2][p][z]+mod)*2%mod);
}
for(int x=0;x<=r;x++) for(int y=0;y<3;y++) dp[r][x][y]=(dp[r-1][x][y]+fp[now][x][y])%mod;
}
ll ans=0;
for(int i=0;i<3;i++) Add(ans,fp[now][1][i]);
ans=(ans%mod+mod)%mod;
for(int i=1;i<n;i++) ans=ans*i%mod;
printf("%lld\n",ans);
return 0;
}
|