D

问有长度为n(2e3)的排列,满足每个位置上$|p_i - i| \neq K$

DP 容斥

K = 0 的时候不就是错位排列么~
先回忆一下二项式反演推错位排列
很自然想到看了题解得到 一个式子
设$f_k$为恰有k个位置满足$|p_i - i| = K$的排列

$ans = \sum_{k=0}^n f_k(n-k)!(-1)^k$

现在的问题就在如何求$f_k$,题解只说了能用一个很!简!单!(个毛线)的DP
然而…智商是硬伤,看了昂神的代码才学会了这个方法

将$i$与$i’-R$还有$i’+R$连边(注意在范围内才能连),就是一个2N个节点的二分图
$f_k$就是匹配数为k的方案数
观察一下,发现互相影响的只有$i,i+k,\dots,i+tk$
所有我们将二分图分成k组,发现互相影响当前$i$匹配的只有$i-k$和$i+k$
因此用一个两位二进制来表示当前位和前一位的匹配情况
有一个技巧就是分k组做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
d[p][0][0] = 1;
F(i,1,K)
{
for(int j=i;j<=N;j+=K)
{
p ^= 1;
memset(d[p],0,sizeof d[0]);
F(k,0,N) F(l,0,3)
{
LL& w = d[p^1][k][l];
if(!w) continue;
add(d[p][k][(l<<1)&3],w); // unmatch
if(!(l&2) && j - K > 0)
add(d[p][k+1][(l<<1)&3],w); // match with j - K
if(j + K <= N)
add(d[p][k+1][((l<<1)|1)&3],w); // match with j + K
}
}
p ^= 1;
memset(d[p],0,sizeof d[0]);
F(k,0,N) F(l,0,3)
{
if(!d[p^1][k][l]) continue;
add(d[p][k][0],d[p^1][k][l]);
}
}

复杂度$O(n^2)$