Problem Statement
Find the number, modulo $998244353$, of permutations $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$ such that:
- $|P_i - i| \ge X$ for all integers $i$ with $1 \le i \le N$.
Constraints
- $1 \le N \le 100$
- $1 \le X \le 5$
- All input values are integers.
但是 \(p_i-i\ge X\) ? 考虑容斥。
定义 \(dp_{i,j,s}\) 为目前选的集合为 \(s\)，选到第 \(i\) 个数，目前有 \(j\) 个不满足要求。
考虑这个是否满足要求，如果不满足，那么记到状压里面，否则就先放着不管
在最后统计答案的时候， \(dp_{n,j,s}\) 中还有 \(n-j\) 个数没有安排好，乘以个 \((n-j)!\)，同时这是一个二项式反演一样的容斥，所以乘上系数 \(C_{n,j}\times (-1)^j\)
#include<bits/stdc++.h>
using namespace std;
const int N=105,S=1025,P=998244353;
int dp[N][S][N],n,m,x,ans,f[N];
int main()
{
scanf("%d%d",&n,&x),--x;
m=x<<1|1;
dp[0][0][0]=1;
for(int i=f[0]=1;i<N;i++)
f[i]=1LL*f[i-1]*i%P;
for(int i=1;i<=n;i++)
{
for(int s=0;s<(1<<m);s++)
{
for(int j=0;j<=i;j++)
{
if(!(s>>(m-1)&1))
dp[i][s][j]=(dp[i-1][s<<1|1][j]+dp[i-1][s<<1][j])%P;
if(j)
{
for(int l=max(1-i,-x);l<=min(x,n-i);l++)
{
if(!(s>>l+x&1))
continue;
int ps=s^(1<<l+x);
if(!(ps>>(m-1)&1))
(dp[i][s][j]+=(dp[i-1][ps<<1|1][j-1]+dp[i-1][ps<<1][j-1])%P)%=P;
}
}
}
}
}
for(int i=0;i<(1<<m);i++)
for(int j=0;j<=n;j++)
(ans+=(j&1? P-1LL:1LL)*dp[n][i][j]%P*f[n-j]%P)%=P;
printf("%d",ans);
return 0;
}