给出 n n 和 ，求有多少个长度为 n n 的排列 使得任意的 1⩽i⩽n 1 ⩽ i ⩽ n ，满足 |ai−i|≠k | a i − i | ≠ k
2⩽n⩽2000 2 ⩽ n ⩽ 2000 ， 1⩽k<n 1 ⩽ k < n
很显然本题正着做很麻烦，于是我们考虑容斥的方法。
记 f(i) f ( i ) 表示至少有 i i 个位置不满足条件的方案数，则答案为
注意到对于每个数，与它的差的绝对值为 k k 的数不超过 个，也就是说如果在 x x 和 之间连边，那么会形成 k k 条链，每个点只能和与它有相连的边配对（如果要不满足条件， 要放在下标为 x±k x ± k 的位置）。
考虑对每条链 DP DP ，设 f[i][j] f [ i ] [ j ] 表示前 i i 个点选了
个不满足条件的数的方案数。
但是注意到一点：每个数 x x 可以和
配对，所以我们需要记录下当前点和下一个点是否被配对。
考虑对于每条链 DP DP ，我们记 f[i][j][p][q] f [ i ] [ j ] [ p ] [ q ] 表示前 i i 个点选了
个不满足条件的数，当前数字 x x 和下一个
是否被选上的方案。
具体 DP DP 转移详见代码（注意有些转移要求差为 k k ）。
时间复杂度：
#include <cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
const int N=2005;
const int P=924844033;
int n,k,a[N],fac[N];
long long f[N][N][2][2];
bool vis[N];
int main() {
scanf("%d%d",&n,&k);
fac[0]=1;
FOR(i,1,n) fac[i]=1LL*fac[i-1]*i%P;
int tot=0;
FOR(i,1,n) if(!vis[i]) for(int j=i;j<=n;j+=k) vis[j]=1,a[++tot]=j;
f[0][0][0][0]=1;
a[0]=-(1<<30);
FOR(i,1,n) {
f[i][0][0][0]=1;
FOR(j,1,i) {
f[i][j][0][0]=(f[i-1][j][1][0]+f[i-1][j][0][0]+(a[i]-a[i-1]==k)*f[i-1][j-1][0][0])%P;
f[i][j][0][1]=(a[i+1]-a[i]==k)*(f[i-1][j-1][1][0]+f[i-1][j-1][0][0])%P;
f[i][j][1][0]=(f[i-1][j][0][1]+f[i-1][j][1][1]+(a[i]-a[i-1]==k)*f[i-1][j-1][0][1])%P;
f[i][j][1][1]=(a[i+1]-a[i]==k)*(f[i-1][j-1][0][1]+f[i-1][j-1][1][1])%P;
}
}
int ans=0;
FOR(i,0,n) {
int sum=(f[n][i][0][0]+f[n][i][0][1]+f[n][i][1][0]+f[n][i][1][1])%P;
if(i&1) (ans+=P-1LL*sum*fac[n-i]%P)%=P;
else (ans+=1LL*sum*fac[n-i]%P)%=P;
}
printf("%d\n",ans);
return 0;
}01.普通输入框字段校验测试1. 不输入，空内容2. 输入1个字符 3. 若输入框有长度限制为N个字符，测试N-1个字符，N个字符，N+1个字符，N+N+...（超长）这几个边界值 4. 还需要测试下通过复制大于长度的值粘贴进去看是否能输入5. 输入半角/全角空格 6. 输入半角/全角，大写/小写英文字符 7. 输入半角/全角数字 8. 输入简体中文字符（...
在微服务场景中，身份认证通常是集中处理，这也是有别于单体应用一把梭哈的模式，其中，在微软微服务白皮书中，提供了两种身份认证模式：网关，没错，原话是If you're using ...
background-position ：背景图像的定位位置属性。 css世界中，background-position 属性设置背景图像的位置属性。这个属性设置背景原图像的位置，背景图像如果要重复，将从这一点开始。另外需要注意的点是把background-attachment 属性设置为 "fixed"，才能保证该属性在 Firefox 和 Opera 中正常工作。 ...
axios封装1、axios的封装1、axios的封装之前在vue里我们使用过axios发请求，但是在实际开发中，都会对axios进行封装。步骤较简单：在src目录下创建utils/service.js路径；import axios from "axios"// 创建axios 赋值给常量service const service = axios.create({ baseURL: 共同的路径(url), timeout: （超时时间，纯数字，单位毫秒） head
记录一下查看自己Ubuntu系统中安装的OpenCV、Eigen、ceres的版本。 目录 1.查看OpenCV版本：2.查看Eigen版本：3.查看cere-solover版本： 1.查看OpenCV版本： 打开终端，运行以下指令： pkg-config --modversion opencv1 如下图所示，我的版本为3.3.1. 2.查看Eigen版本： 打开终端： sudo gedit /usr/include/eigen3/Eigen/src/Core/util/Ma.
修改点击显示的infoBox内容
文章目录基础知识泛型可变参基础知识泛型常用的通配符有T,E,K,V分别表示类型、元素、键、值E 未知的数据类型,在集合中使用T - Type（Java 类） 方法前等等使用可变参* 前提：方法的参数数据类型确定，参数的个数任意* 可变参的语法个数：数据类型…变量名* 可变参数本质上就是一个数组...
当从远程svn拉取项目，出现文件中没有.iml文件，这种情况是别人提交时候给忽略掉了，导致导入项目到idea时候，发现只有pom.xml文件，其他的文件依赖什么的，都显示不出来，如何出现完整项目呢?变为正常项目呢？跟着我操作： 第一步：点击项目右边，有个Mavenpeoject侧边栏，这时候有个Ignore Projects按钮。 这时候点击一下，会变成unig...
导语|本文主要介绍webpack的打包流程，及其插件系统Tabable，并手写了一下简易打包器。通过这篇文章读者可以了解webpack的具体实现过程，并且自己也可以理解其打包原理，有利...
解题思路：由于一次过桥最多两个人，且手电筒需要往返传递，因此以两个成员过桥为一个分析单位，计算过桥时间，我们按照过桥时间递增的顺序将n个成员排序，设当前序列中，A是最快的人，B是次快的人，a是最慢的人，b是次慢的人。又两种过桥方案：（1）用最快的成员传递手电筒帮助最慢和次慢的人过桥，所有时间为2*A+a+b;（2）用最快和次快的成员传递手电筒帮助最慢和次慢的人过桥：步骤如下
纯前端导出表格，vue导出excel表格，react导出excel表格
本篇介绍策略、两种值函数（状态值函数和动作值函数），以及大名鼎鼎的贝尔曼方程。补充了一点关于贝尔曼方程的推导过程，希望能够帮助理解。本文中公式编号(,)中第2部分表示对应公式（如果在原书中有的话）在原书中的编号。