Change log

• 2023.10.25 修改少量 MarkDown 的使用。

$\color{blueviolet}\text{POI 套题集合（点我）}$

$\color{red}\text{博客内食用效果更佳（点我）}$

时间复杂度：$O(n)$

完整思路

观察到 $p$ 的范围很小，我们尝试进行分类讨论。

---

当 $p=0$：
显著地，当且仅当 $n=1$ 时答案为 $1$，剩余情况为 $0$。

---

当 $p=1$：
同样显著地，此时当且仅当 $n=1\lor(n=2\land k=0)$ 时答案为 $1$，剩余情况为 $0$。

---

当 $p=2$：
考虑先放置 $n$，它两侧只有可能是 $n-1,n-2$，$n-1$ 旁边只有可能放 $n-3$，$n-2$ 旁边只有可能放 $n-3$，以此类推，这种情况下只有顺时针逆时针两种情况，构造并判断即可。

---

当 $p=3$：
我们尝试从 $n$ 至 $1$ 依次放进环内，考虑当前放置到编号为 $i$ 的，显然它只能和 $i+1,i+2,i+3,i-1,i-2,i-3$ 相邻，我们只需要考虑 $i+1,i+2,i+3$，它们都在环内，而 $i-1,i-2,i-3$ 的情况会在放入它们的时候考虑。

我们现在考虑两个问题：

• $i+1,i+2,i+3$ 两两之间可能有已经放入的点，在此种情况中我们无法将 $i$ 插入到这种位置，因为这显著是不合法的。
• 当我们放入 $i$ 后，$i+3$ 不能和接下来要放入的点相邻，这就意味着 $i+3$ 一定要紧挨着两边的点，我们需要判断此时 $i+3$ 的状态。（这种情况会产生上一个问题，可以理解为 $i+3$ 与两边合并，使这一段不能放置接下来的东西）。

现在给出以下约定方便表述：

• $i+1,i+2$ 之间为位置 $1$，$i+2,i+3$ 之间为位置 $2$，$i+3,i+1$ 之间为位置 $3$。
• 设 DP 状态 $f_{i,j,st}$ 表示放置完编号 $i$ 的东西，是否是逆时针（$j$），$i+1,i+2,i+3$ 之间的位置状态为 $st$（对位置 $1,2,3$ 状态进行状压，分别对应 $1,2,4$）。
• $\mathrm{sit}(x,y)$ 表示 $x$ 是否能坐在 $y$ 右侧，合法为 $1$，不合法为 $0$。
• $1\in st$ 表示位置 $1$ 在当前状态中是可行的，其他表达同理。

对于状态 $f_{i+1,j,st}$ 我们尝试向下转移。

若位置 $1$ 可放置（以下讨论均基于顺时针，逆时针只需要将所有状态置反即可）：

$i+3$ 需要和 $i+1,i+2$ 合并，两者合并当且仅当两者之间已经有其他东西或两者可以相邻，我们可以得到以下约束。

$$\left(2\notin st\lor\mathrm{sit}(i+2,i+3)\right)\land\left(3\notin st\lor\mathrm{sit}(i+3,i+1)\right)$$

放置到位置 $1$ 后我们的状态变为 $f_{i,j\oplus1,5}$（首先这种放置显著会改变顺逆状态，其次这种放置状态下使得 $i,i+1$ 以及 $i,i+2$ 之间的空位可用。），可以得到以下转移。

$$f_{i,j\oplus1,\{1,3\}}=f_{i,j\oplus1,\{1,3\}}+f_{i+1,j,st}$$

若位置 $2$ 可放置：

得到以下约束以及转移。

$$\mathrm{sit}(i,i+3)\land\left(2\notin st\lor\mathrm{sit}(i+2,i+3)\right)$$

设 $st'$ 表示改变后的状态，若 $1\in st$，则 $st'=\{2,3\}$，否则 $st'=\{3\}$。

$$f_{i,j,st'}=f_{i,j,st'}+f_{i+1,j,st}$$

若位置 $3$ 可放置：

得到以下约束以及转移。

$$\mathrm{sit}(i+3,i)\land\left(3\notin st\lor\mathrm{sit}(i+3,i+1)\right)$$

设 $st'$ 表示改变后的状态，若 $1\in st$，则 $st'=\{1,2\}$，否则 $st'=\{1\}$。

$$f_{i,j,st'}=f_{i,j,st'}+f_{i+1,j,st}$$

---

大部分转移已经讨论完毕，最后一层还需约束放置完的左右关系，与上述约束、转移类似，就不进行冗杂的讨论了。

代码实现需要注意的地方：

• 别忘记取模。
• 对于初值有 $f_{n-2,0,7}=1,f_{n-2,1,7}=1$。

参考代码：

#include<bits/stdc++.h>
#define LL long long
#define UN unsigned
using namespace std;
//--------------------//
const int N=1e6+5,Mod=1e9+7;

int n,k,p,f[N][2][8];
bool ht[N][10];
void add(int &x,int y){x+=y,x-=((x>=Mod)?Mod:0);}//优化取模
bool sit(int x,int y){return abs(x-y)<=p&&!ht[y][y-x+3];}//判断是否能坐在右面
bool ck1(int i,int j,int st,int pos)//判断是否合法
{
	if(j)
	{
		if(pos==1)
			return ((!(st&4)||sit(i+3,i+1))&&(!(st&2)||sit(i+2,i+3)));
		if(pos==2)
			return (sit(i,i+3)&&(!(st&4)||sit(i+3,i+1)));
		return (sit(i+3,i)&&(!(st&2)||sit(i+2,i+3)));
	}
	if(pos==1)
		return (!(st&4)||sit(i+1,i+3))&&(!(st&2)||sit(i+3,i+2));
	if(pos==2)
		return (sit(i+3,i)&&(!(st&4)||sit(i+1,i+3)));
	return (sit(i,i+3)&&(!(st&2)||sit(i+3,i+2)));
}
bool ck2(int i,int j,int st,int pos)//判断 i=1 时是否合法
{
	if(i>1)
		return true;
	if(j)
	{
		if(pos==1)
			return (sit(1,3)&&sit(2,1));
		if(pos==2)
			return (sit(3,1)&&(!(st&1)||sit(2,3)));
		return (sit(1,2)&&(!(st&1)||sit(2,3)));
	}
	if(pos==1)
		return (sit(3,1)&&sit(1,2));
	if(pos==2)
		return (sit(1,3)&&(!(st&1)||sit(3,2)));
	return (sit(2,1)&&(!(st&1)||sit(3,2)));
}
//--------------------//
int main()
{
    scanf("%d%d%d",&n,&k,&p);
    for(int x,y,i=1;i<=k;i++)
    {
        scanf("%d%d",&x,&y);
        if(abs(x-y)<=p)
            ht[x][x-y+3]=true;
    }
    if(p==0)//分讨
    {
        if(n==1)
            printf("1");
        else
            printf("0");
        return 0;
    }
    if(p==1)
    {
        if(n==1||(n==2&&k==0))
            printf("1");
        else
            printf("0");
        return 0;
    }
	if(n==1)
		printf("1");
	if(n==2)
		printf("%d",k?0:1);
	if(n<3)
		return 0;
    if(p==2)
    {
        int ans=0;
        //顺时针
        bool flag=((!sit(n-1,n))|((n&1)&&!sit(1,2))|((!(n&1))&&!sit(2,1)));
        for(int i=n-1;i>2;i-=2)
            flag|=!sit(i-2,i);
        for(int i=n-2;i>2;i-=2)
            flag|=!sit(i,i-2);
        //逆时针
        ans+=!flag,flag=((!sit(n,n-1))|((n&1)&&!sit(2,1))|((!(n&1))&&!sit(1,2)));
        for(int i=n-1;i>2;i-=2)
            flag|=!sit(i,i-2);
        for(int i=n-2;i>2;i-=2)
        	flag|=!sit(i-2,i);
        ans+=!flag;
        printf("%d",ans);
        return 0;
    }
	f[n-2][0][7]=f[n-2][1][7]=1;
	for(int i=n-2;i>=2;i--)//倒序转移
	{
		for(int j=0;j<=1;j++)
		{
			for(int st=0;st<=7;st++)
			{
				if(!f[i][j][st])
					continue;
				if((st&1)&&ck1(i-1,j,st,1)&&ck2(i-1,j,st,1))
					add(f[i-1][j^1][5],f[i][j][st]);
				if((st&2)&&ck1(i-1,j,st,2)&&ck2(i-1,j,st,2))
					add(f[i-1][j][4|((st&1)<<1)],f[i][j][st]);
				if((st&4)&&ck1(i-1,j,st,3)&&ck2(i-1,j,st,3))
					add(f[i-1][j][1|((st&1)<<1)],f[i][j][st]);
			}
		}
	}
	int ans=0;
	for(int i=0;i<=7;i++)//统计答案
		add(ans,f[1][0][i]),add(ans,f[1][1][i]);
	printf("%d",ans);
    return 0;
}