QOJ 8351 Ruin the legend
题意
给定一个正整数序列 \(a\) 和一个正整数 \(k\)，保证 \(a_i\) 严格单调递增，求有多少长度为 \(n\) 的序列 \(p\) 满足：
-
\(p\) 是一个 \(a\) 重排后得到的序列。
-
对于任意 \(1\le i< n\)，\(|p_i-p_{i+1}|\neq k\)。
\(n\le 5000\)。
题解
知识点：动态规划。
计数。
\(a_i\) 两两不同，所以满足 \(|a_i-a_j|\) 的 \((i,j)\) 是 \(O(n)\) 级别的，下称这样的东西为一组限制。
假如对于每个上述 \((i,j)\)，在 \(i,j\) 之间连一条无向边，组成一张无向图，则会得到若干连通块，且每个连通块都是一条链。
链上元素的顺序是有意义的，相邻两个节点代表的 \(a_i\) 之间的差值都是 \(k\)，也就是说所有相邻的两个元素都形成了一组限制。
一种处理出所有链的简单方法就是将 \(a\) 升序排序，其中第一关键字为 \(a_i\bmod k\)，第二关键字为 \(a_i\)，这样每条链在 \(a\) 中就是连续的一段。
正着做，还是太困难了，考虑求出不合法的方案数。
一种可能的想法是设计 \(g_{i}\) 表示恰好有 \(i\) 个限制不满足的情况下，\(p\) 的方案数。
但这其实和正着做没什么区别，还是非常难，考虑容斥。
设 \(g_i\) 表示钦定有 \(i\) 个限制不满足，其他随便（也就是说除了钦定之外的限制也可能不被满足）的情况下，\(p\) 的方案数。
那么答案就是 \(\displaystyle \sum_{i=0}^n (-1)^{i} g_i\)。
为了求出 \(g_i\)，需要设计 dp 状态和转移来计算。
首先肯定是从排序后的 \(a\) 从 \(1\) 到 \(n\) 一步一步推过去。
当位于满足 \(a_i-a_{i-1}=k\) 的 \(i\) 时，\(i\) 和 \(i-1\) 可以形成限制，此时就涉及到了形成或者不形成的决策。
同时，由于限制是带绝对值的，如果 \(a_i-a_{i-1}=k\)，则把他们正着排反着排都是可行的，且贡献了两种方式。
\(0\) 与 \(1\) 不可能形成限制，所以赋值 \(a_0=-\infty\)。
需要注意的时，对于一个决定和 \(i-1\) 形成限制的 \(i\)，如果从 \(i-1\) 与 \(i-2\) 选择形成限制的局面转移过来，则不能将其像上文一样随意排列。
宏观地来看，一条链（不仅可以是上文连出的无向图上的一条完整的链，也可以是其子链）在 \(p\) 上的排列方向是正向和反向，不可能说里面的节点又正又反，这也太抽象了。
所以设计 \(f_{i,j,0/1}\) 表示前 \(i\) 个元素，钦定了 \(j\) 个限制不满足，当前 \(i\) 与 \(i-1\) 选择形成限制（第三维为 \(1\)），或者不形成限制（为 \(0\)）的方案数。
有转移：
关于系数 \((i-j)\) 的含义，如果把之前选择形成限制的 \(k\) 和 \(k-1\) 缩成一个位置的话，就是可以与 \(i\) 交换的位置数，本质上就是生成排列的组合意义。
细心读者可能会对上面这段话存疑，\(i-j\) 代表位置数减去形成的限制数，如果两段重叠（如 \(1,2\) 和 \(2,3\)，那么 \(2\) 就不能换了），可以交换的位置数难道不是 \(<i-j\) 的嘛？事实上并不是，仔细琢磨一下，如果有重叠一个位置，那有空出一个位置，两者重叠，还是 \(i-j\)。
代码使用了刷表法实现转移。
#include<bits/stdc++.h>
using namespace std;#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()#define N 5005
#define int long longconst int mod=998244353;int n,k,a[N],f[2][N][2];inline int ng(int x){return x&1?mod-1:1;
}inline void add(int &x,int y){x=(x+y+mod)%mod;
}signed main(){// freopen(".in","r",stdin);// freopen(".out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;a[0]=-697891;rep(i,1,n){cin>>a[i];}sort(a+1,a+1+n,[](int x,int y){if(x%k==y%k){return x<y;}return x%k<y%k;});f[0][0][0]=1;rep(i,0,n-1){int ns=i&1,nx=ns^1;rep(j,0,i){add(f[nx][j][0],f[ns][j][0]*(i+1-j));add(f[nx][j][0],f[ns][j][1]*(i+1-j));if(a[i+1]-a[i]==k){add(f[nx][j+1][1],f[ns][j][0]*2);add(f[nx][j+1][1],f[ns][j][1]);}f[ns][j][0]=f[ns][j][1]=0;}}int ans=0,ns=n&1;rep(i,0,n){add(ans,ng(i)*(f[ns][i][1]+f[ns][i][0])%mod);}cout<<ans<<'\n';return 0;
}